Python数组中求和问题

作者：dyq666，zhihu.com/people/dyq666

本专题主要介绍哈希表和指针两种方法来解决该类问题，从两个数之和引申到三个数之和，再从四个数之和的问题上思考如何构建出一种通用的代码（可以解决N个数之和）。本文主要内容是通过001问题来初步了解数组求和的两种常用方法。

001-Two Sum

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例 :

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

1. 暴力循环

O(n^2)

唯一需要注意的是同一个元素不能复用

2. 哈希

（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中存放的肯定是前一个值（因为是之前遍历过的）。

3. 双指针

（1） O(nlogn)-主要是快排的影响

（2） 在一个有序的数组中最左边一定是最小值，而最右边一定是最大值。我们可以将最小值与最大值相加与目标值进行比较，如果两数之和大于目标值，我们就让最大值小一点（也就是读取第二个最大值），相反如果小于，则让最小值大一点（读取第二个最小值）。这样我们就保证了一次循环就能查找到目标值，但数组必须是有序的。

回到题目中:

（1） 由于需要返回索引，所以我们必须存储两个数组，一个是无序的（用于查找真实的索引），另一个是有序的（用于查找符合题目的值）。

（2） 两个指针left和right分别指向数组中第一个元素和最后一个元素（最小值和最大值）

（3） 循环的结束条件为左指针大于等于右指针（左边的不能比右边的大，而且一个元素只能用一次）

（4） 然后就判断左值+右值与目标值之间的关系，在上面我们已经讨论过了大于和小于的情况。

（5） 当等于时由于我们需要得到左值和右值在原本数组的索引，我们需要考虑以下问题。从题目中的得知每个target只有一个答案, 意味着如果target是6不会出现[2, 2, 4]的情况, 但是会出现[3, 3]的情况, 也就是当两个相同的值满足情况是才会有重复的元素。所以我们先通过index获取左值对应的索引，如果左值和右值相同我们就获取下一个该值的索引，如果不同，我们直接获取右值相关的索引。

总结

通过两个数求和问题初步了解数组求和问题，下一文将引申这两种方法在三个数求和中的应用。