题目描述：
给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路
1. 暴力解法
刚看完题目时，我第一个想到的是暴力解法，即遍历数组，当前数与后面位置的数字相加，看是否等于target，由此可以写出如下解：
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(0, len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]此时的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。
那么有没有更快一点的方法？
2. 哈希表
暴力解法的第二次遍历可以改进下，引入哈希表，将所有数装入哈希表，此时在遍历数组时，查看target-num是否在哈希表中，此时代码如下：
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {}
for i in range(0, len(nums)):
dict[nums[i]] = i
for i in range(0, len(nums)):
find = target - nums[i]
if find in dict.keys() and i != dict[find]:
return [dict[find], i]哈希表的查找效率为$O(1)$，因此算法的时间复杂度为$O(n)$，由于引入哈希表，空间复杂度取决于数组的长度n，因此空间复杂度为$O(n)$，用空间换取时间。
这种方式有个问题，假如数组中有重复数字，那存入哈希表后，重复的数字就会被丢弃，如：nums = [2,3,3], target = 6，此时正解为[1,2]，但由于哈希表中的项无重复，第二个3并不会存入哈希表，导致无解，下面看如何解决这个问题。
3. 哈希表-改进
上述方法是在将所有数字存入哈希表后，再遍历比较，导致重复值被丢弃。
可以继续改进下，遍历数组的同时，与已存入哈希表中的数据进行对比，若不存在再存入哈希表，这样就将比较阶段提前到哈希表的put动作之前，从而解决上述问题。
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = {}
for i in range(0, len(nums)):
find = target - nums[i]
if find in dict.keys() and i != dict[find]:
return [dict[find], i]
else:
dict[nums[i]] = i
本文由 花墨 创作，采用 知识共享署名4.0 国际许可协议进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。