转发：https://lefttree.gitbooks.io/leetcode-categories/content/sum/kSum.html
求和问题总结
题目列表
- 2 sum
- 2 sum II - input array is sorted
- 2 sum III - data structure design
- 3 sum
- 3 sum closest
- 3 sum smaller
- 4 sum
- k sum
- k sum II
问题描述
一般是给一组n个数字，给1个target, 求出k个数字的sum为target. 有变化的题目就是求closest，求个数，求组合等等
注意事项
- 可能有重复项，注意去掉重复的组合, 除了2sum的题目最好先sort一下，这样可以方便去掉重复的项
- sort方法枚举的时候注意不要重复，就像subsets一样
2 sum 解法
方法1 - brute force
枚举所有的k-subset, time complexity就是从N中选出k个,
O(n^k)方法2 - 先sort,再two pointer
O(NlogN + N) = O(nlogn), 要注意的是sort了之后就改变了原来的顺序
方法3 - hashmap O(n)
对于2 sum来说，其实就是对于每一个element
nums[i], 在数组中找是否存在target - nums[i]
用hashmap保存访问过的value, 对每个
num[i],检查hashmap中是否有target - nums[i],扫完一遍就能够得到结果。属于用空间换时间。
time complexity -
O(n) space complexity - O(n)后续题目
对于two sum的题目
- 如果是要返回index,那么优先用hashmap的做，因为不会改变原来array的顺序
- 如果是返回元素的value,那么可以用先sort然后two pointer的方法
对于3sum, 3sum closest, 4sum等题目，因为大部分都是根据two sum two pointer做法的延伸，所以都是要求return value
summary
two pointer
two pointer做法有利于跳过重复元素，用来计算closest, smaller等等不等于target的题目，所以优先使用
3 sum 解法
3 sum 可以退化为2 sum， 先取出一个数i, 然后在剩下的数组中找sum为
target - i的就可以了。
这里要注意的是不管采取sort还是hashmap的方法，时间复杂度其实都是
O(n^2). hashmap的大家都知道，排序的解释如下：排序
sort只sort一遍 O（nlogn), 然后每一个取出一个数，再two pointer寻找的复杂度是O(n^2)
总的复杂度是 O(nlogn + n^2) = O(n^2)
3 sum closest解法
3 sum closest的解法为采取类似3 sum, 但是不要用hashmap, 用
sort + two pointer的方法可以方便的找到closest4 Sum
4 sum退化为3 sum， 可以用两个for loop内部再2 sum的方法来做
O(n^3)K sum
K sum也一步步退化，最终变为2 sum
K sum的时间复杂度是
O(n^(k-1))补充
什么时候去重？
- 如果问题问的是Index的组合，就没有必要去重
- 如果问题问的是值的组合，就需要去重
去重的方法：
if ((l != start) && (nums[l] == nums[l - 1])) {
l++;
} else if ((r != end) && (nums[r] == nums[r + 1])) {
r--;
} else {
// Process the nums as the normal 2 sum
}
如果用If语句，注意加上continue
3 Sum Closest:
思路和3 Sum一样，主要是找到那个交叉点（l < r)。只要这个点交叉了，那么所有可能的最接近的sum就都被evaluated. l++, r--的方式就是逐个逼近target。
还有一道是K SUM题目，可以转换为背包问题。
