1.两数之和
题目:
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
代码:
class Solution: def twoSum(self, nums, target): # 使用字典来保存 数字:索引 hashmap = {} # 创建 数字:索引 键值对 for ind, num in enumerate(nums): hashmap[num] = ind # 循环,从中获取target-num对应的index,但是index不能和i相等,因为一个数不能使用两次 for i, num in enumerate(nums): j = hashmap.get(target - num) if j is not None and i != j: return [i, j] if __name__ == '__main__': s = Solution() print(s.twoSum([3, 3, 4, 3], 6)) # 返回[0,3],而不是[0,1]
总结:
# 该题可以使用暴力法来解答,即双层循环一个一个试,直到找到2个数加起来等于target,但是效率很低下 # 使用enumerate将数组转化为字典,利用字典的get方法,可以很快判断字典中是否存在想要的值,大大提高运行效率,但是会浪费内存空间
2.
###