本专题主要介绍哈希表和指针两种方法来解决该类问题，从两个数之和引申到三个数之和，再从四个数之和的问题上思考如何构建出一种通用的代码（可以解决N个数之和）。本文主要内容是通过001问题来初步了解数组求和的两种常用方法。
001-Two Sum
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例 :
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
- 暴力循环
O(n^2)
唯一需要注意的是同一个元素不能复用
nums_len = len(nums)
for
i
in
range(
0
, nums_len):
for
j
in
range(i +
1
, nums_len):
if
nums[i] + nums[j] == target:
return
[i, j]
- 哈希
（1） O（n）
（2） 考虑暴力循环中我们做的事情，我们先挑出一个值a，然后看数组中其他值是否能与值a相加等于目标，也可以说成看数组中是否存在一个值等于目标值减去值a。
（3） 换个思路，我们将所有遍历过的值存放起来，每次遍历到一个新的值b时，我们可以查找目标值减去值b是否在我们存放的值中。基于哈希表的特性，查找的时间复杂度为O（1），总时间复杂度就变为了一次for循环O（n）
回到本道题中:
（1） 由于需要返回对应的索引，所以需要使用HashMap（在python中是dict），key存放数组中的值，value存放数组中的索引，遍历数组，将遍历过的值存入dict，如果目标值减去当前值在dict中则证明找到了目标值。
（2） 还有一点需要注意的是如果想按从小到大的顺序返回值，dict中存放的肯定是前一个值（因为是之前遍历过的）。
seen_dict = {}
for
i, num
in
enumerate(nums):
search = target - num
if
search
in
seen_dict:
return
[seen_dict[search], i]
else
:
seen_dict[num] = i
- 双指针
（1） O(nlogn)-主要是快排的影响
（2） 在一个有序的数组中最左边一定是最小值，而最右边一定是最大值。我们可以将最小值与最大值相加与目标值进行比较，如果两数之和大于目标值，我们就让最大值小一点（也就是读取第二个最大值），相反如果小于，则让最小值大一点（读取第二个最小值）。这样我们就保证了一次循环就能查找到目标值，但数组必须是有序的。
回到题目中:
（1） 由于需要返回索引，所以我们必须存储两个数组，一个是无序的（用于查找真实的索引），另一个是有序的（用于查找符合题目的值）。
（2） 两个指针left和right分别指向数组中第一个元素和最后一个元素（最小值和最大值）
（3） 循环的结束条件为左指针大于等于右指针（左边的不能比右边的大，而且一个元素只能用一次）
（4） 然后就判断左值+右值与目标值之间的关系，在上面我们已经讨论过了大于和小于的情况。
（5） 当等于时由于我们需要得到左值和右值在原本数组的索引，我们需要考虑以下问题。从题目中的得知每个target只有一个答案, 意味着如果target是6不会出现[2, 2, 4]的情况, 但是会出现[3, 3]的情况, 也就是当两个相同的值满足情况是才会有重复的元素。所以我们先通过index获取左值对应的索引，如果左值和右值相同我们就获取下一个该值的索引，如果不同，我们直接获取右值相关的索引。
raw_nums = nums
nums = sorted(nums)
left, right =
0
, len(nums) -
1
while
left < right:
v_left, v_right = nums[left], nums[right]
two_sum = v_left + v_right
if
two_sum > target:
right -=
1
elif
two_sum < target:
left +=
1
else
:
# 找到了
left_index = raw_nums.index(v_left)
# 如果值相同就查找下一个该值的索引
right_index = raw_nums.index(v_right, left +
1
)
if
v_right == v_left
else
raw_nums.index(v_right)
return
[left_index, right_index]
总结
通过两个数求和问题初步了解数组求和问题，下一文将引申这两种方法在三个数求和中的应用。
原文发布时间为：2018-08-04
本文作者：dyq666
本文来自云栖社区合作伙伴“ Python中文社区”，了解相关信息可以关注“ Python中文社区”
