Two Sum
你会得到一个整数数组 nums 和一个整数 target。nums 中恰好有两个元素位于不同的位置，它们的和等于 target。返回这两个元素的索引，较小的索引在前。
函数
- numsinteger-array
- 要搜索的整数数组
- targetinteger
- 两个条目的总和必须达到
- 返回值integer-array
- 这两个索引，较小的在前
约束条件
2 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- 恰好有一对不同的位置之和等于
target。
示例
- 输入
- nums = [3, 8, 12, 5]target = 17
- 输出
- [2, 3]
- 解释
- 12 位于索引 2，5 位于索引 3，并且 12 + 5 = 17。没有其他数对的和是 17。
- 输入
- nums = [6, 1, 4, 10]target = 7
- 输出
- [0, 1]
- 解释
- 索引 0 处的 6 和索引 1 处的 1 相加等于 7：这两个数可以作为前两个元素。
- 输入
- nums = [2, -6, 9, 4, 13]target = 3
- 输出
- [1, 2]
- 解释
- 索引 1 处的 -6 和索引 2 处的 9 相加等于 3。负数和正数的配对方式相同。
进阶
如果 nums 已经排好序，你能否只用 O(1) 的额外内存，在 O(n) 时间内找到这一对数？
提示
逐个打开提示，每个都会多透露一点。
用两个嵌套的循环尝试每一对数字是正确的，但对于 10,000 个数字，这大约需要检查 5000 万次。你能不再扫描列表，找到每个数字的配对数字吗？
当你看到一个值
x时，你已经知道哪个值能与它组成一对：目标值减去x。唯一的问题是，你之前是否见过这个值，以及它位于哪个索引。遍历列表一次，并用哈希映射记录你已遍历过的每个值及其索引。在每个位置，先查找缺少的配对值；如果它在映射中，你就找到了两个索引。否则，存储当前值并继续遍历。先查找再存储，这样可以避免一个数字与自身配对。
题解
检查每一对数字是可行的，但工作量会随着长度的平方增长。换个角度思考：对于数字 x，你已经知道它的配对数字必定是 target - x。哈希映射可以让你在常数时间内判断是否已经遍历过这个值，因此遍历一遍就够了。
检查每一对
结果正确，但无法在最大的测试中运行完毕
思路
固定第一个索引 i，并尝试它右侧的每个索引 j，直到 nums[i] + nums[j] 等于 target。将 j 从 i + 1 开始，可以避免一个位置与自身配对，确保每对只尝试一次，并让较小的索引排在前面。你要找的那一对就在尝试的组合中，所以你一定能找到它。
n 个数字大约能组成 n²/2 对：n = 10^4 意味着接近 5 × 10^7 次加法。
算法
- 遍历
nums的每个索引，让i依次取值。 - 对于每个
i，让j从i + 1遍历到最后一个索引。 - 如果
nums[i] + nums[j]等于target，就返回[i, j]。 - 如果两个循环都结束了，就返回一个空数组。题目保证这种情况不会发生。
def twoSum(nums, target):
n = len(nums)
for i in range(n):
# Only look at partners to the right, so each pair is checked once.
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []使用哈希映射遍历一次
思路
对于固定的 nums[i]，暴力解法的内层循环会查找一个你预先就知道的值：target - nums[i]。这种扫描其实是在伪装成查找，而从值映射到索引的哈希表平均能以常数时间完成查找。
先查找，再存储。这样，一个数字只能与它之前的数字配对，不能与自身配对；而且由于配对数字总是在前面，它的索引也更小。每个数字只访问一次，哈希表操作的时间复杂度为常数，因此搜索的时间复杂度为 O(n)；代价是哈希表最多需要存储 n 个条目。
算法
- 创建一个空映射，用来存储值及其索引。
- 对于每个索引
i，计算need，也就是能补成一对的值：target减去nums[i]。 - 如果映射中有
need，则返回它存储的索引，后接i。 - 否则，将
nums[i]与索引i一起存入映射，然后继续。
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
need = target - num
if need in seen:
return [seen[need], i]
seen[num] = i
return []
易错点和边界情况
- 先存储数字，再查找与之配对的数字。对于
[4, 2, 6]和target = 8，4 会找到它自己，最后返回[0, 0]。 - 返回的索引顺序错误。先查找再存储时，哈希表中的索引较小，应放在前面。
- 先对数组排序，再使用双指针，最后返回排序后副本中的位置。要把每个值的原始索引保存在它旁边。
- 假设值都是正数或互不相同。对于
[0, 7, -3, 0]和target = 0，配对的是两个 0：[0, 3]。 - 在 Lua 和 R 中返回的是从 1 开始的索引。每个索引都减去 1。
常见问题3
Two Sum 的时间复杂度是多少？
哈希映射解法的时间复杂度为 O(n)，因为它会遍历每个数字一次，并且每次查找或插入的平均时间都是常数。它使用 O(n) 的额外空间来存储映射。检查每一对数字需要 O(n²) 的时间和 O(1) 的空间。
Two Sum 能否在不使用额外空间的情况下解决？
对于未排序的数组，无法在线性时间内完成。使用 O(1) 的额外空间，你就只能重新检查每一对元素，这需要 O(n²) 的时间。哈希映射用 O(n) 的内存换取线性时间。
Two Sum 如何处理重复数字？
在存储当前数字之前先查找配对数字，这样就能处理重复值。在 [7, 3, 7] 中，当 target = 14 时，第一个 7 会存储在索引 0 处，第二个 7 会找到它，得到 [0, 2]。单独的 7 不会和自身配对：查找它时，它还不在映射中。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def twoSum(nums, target):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 8, 12, 5] target = 17
预期输出
[2, 3]