题目
https://leetcode.cn/problems/two-sum/
给定一个整数数组 nums 和一个整数 target ，返回两个数字的索引，使得它们加起来等于 target。
可以假设每个输入都只有一个解 ，并且不能使用同一个元素两次。
可以按任意顺序返回答案。
自解
暴力枚举
1
2
3
4
5
6
| def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if target == nums[i]+nums[j]:
return i,j
return []
|
第一道题，学如何用 for 循环遍历数组。
哈希表（两次迭代） ^a89bdc
[!tip]
在第一次迭代中，将每个元素的值作为键，其索引作为值添加到哈希表中。
在第二次迭代中，检查每个元素的补集（ $target−nums[i]$）是否存在于哈希表中。如果存在，则返回当前元素的索引及其补集的索引。
迭代是指重复执行一段代码的过程，通常是为了遍历某个集合（比如数组、列表）中的每一个元素。
1
2
3
4
5
6
7
8
| def twoSum(self, nums: List[int], target: int) -> List[int]:
harshtable=dict()
for i in range(len(nums)):
harshtable[nums[i]]=i
for i in range(len(nums)):
comp=target-nums[i]
if comp in harshtable and harshtable[comp]!=i:
return i,harshtable[comp]
|
第一次用晕乎乎，不知道哈希表是什么，还把键和值弄反了。
哈希表（一次迭代）
[!tip]
在遍历哈希表并向其中插入元素的之前，回溯检查当前元素的补集是否已存在于哈希表中。如果存在，我们就找到了解决方案，并立即返回索引。
1
2
3
4
5
6
7
8
| def twoSum(self, nums, target):
harshtable=dict()
for i,num in enumerate(nums):
comp = target - num
if comp in harshtable:
return i,harshtable[comp]
harshtable[num]=i
return []
|
内置函数 enumerate 在 for 循环中可以分别得到数组的索引和值。dict 用于创建一个字典。
题解
灵茶山艾府
和官方题解的哈希表差不多，图解会更直观。
1
2
3
4
5
6
7
| def twoSum(self, nums, target):
harshtable=dict()
for i,num in enumerate(nums):
if target-num in harshtable:
return i,harshtable[target-num]
harshtable[num]=i
return []
|
总结：使用哈希表可以以牺牲空间为代价，降低时间复杂度，将时间复杂度降为O(n)，同时空间复杂度变为O(n)。
很多涉及到「两个变量」的题目，都可以枚举其中一个变量，把它当成常量看待，从而转化成「一个变量」的问题。通常来说「枚举右，寻找左」是更加好写的。
相似题目
题单第0.0.1节
和相等的子数组
给你一个下标从 0 开始的整数数组 nums ，判断是否存在 两个 长度为 2 的子数组且它们的 和 相等。注意，这两个子数组起始位置的下标必须 不相同 。如果这样的子数组存在，请返回 true，否则返回 false 。
子序列是一个数组中一段连续非空的元素组成的序列。
https://leetcode.cn/problems/find-subarrays-with-equal-sum/
1
2
3
4
5
6
7
8
9
| def findSubarrays(self, nums: List[int]) -> bool:
hstable=dict()
seen = set()
for i in range(len(nums)-1):
current_sum = nums[i]+nums[i+1]
if current_sum in seen:
return True
seen.add(current_sum)
return False
|
一开始以为子序列可以跳着选，我想的是用两个 for 循环遍历数组，算出所有的的和，记录和的序号，并做比较。
G 老师建议我使用 set（集合），因为题目只要求有没有。如果需要知道索引，还是得用 dict，应该类似上面哈希表的思路。