1. 题目
两数之和
2. 分析
这道题有多种解法，逐个来看。
2.1 深搜版
首先可以用深搜来解，我们从数组集合中选取两个数，判断其和是不是target，如果是则满足要求，如果不是，继续选取。
2.2 循环版
深搜版的代码用在这题上，属实有点儿大材小用了。原因是，我们的搜索空间可以用for循环罗列出来，而不用费劲儿的用深搜。Leetcode 官方题解还给了一个对双重for循环优化的代码，优化的逻辑则是根据题意想出的。
2.3 哈希表版
刷了这道Leetcode后，我反思了一下自己的学习过程，感觉自己进入了旁门左道，一直在追求使用深搜、动态规划这种高逼格的代码，但是有些时候，简单的数据结构使用，就可以迅速降低问题复杂度。
3. 代码
3.1 深搜版
# 使用深搜的方法解决本题，但存在的问题是会导致超时，很多输入过不了，
# 那么就需要考虑其它的解决方法
class Solution:
res = []
def twoSum(self, nums: List[int], target: int) -> List[int]:
self.res = []
cnt = 0
tmp = []
idx = 0 # 起始下标
self.dfs(nums, cnt, tmp, idx, target)
return self.res
# 判断当前下标 = idx 的数
def dfs(self, nums, cnt, tmp, idx, target):
if cnt == 2 and nums[tmp[0]] + nums[tmp[1]] == target:
print(tmp)
self.res = tmp[:]
return
if idx >= len(nums):
return
# 放idx
tmp.append(idx)
self.dfs(nums, cnt+1, tmp, idx+1, target)
del tmp[-1]
# 不放idx
self.dfs(nums, cnt, tmp, idx+1, target)
3.2 循环版
这部分代码略去。
3.3 哈希表版
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 这里只是定义了一个hash表，还没有做放入值的操作。
# 亮点就是这个哈希表的值是边遍历边放入其中。
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
# 存入 nums[i] 的下标
hashtable[nums[i]] = i
return []
