Two Sum类双指针

题目套路

一般给定一个array (sorted or unsorted), 问找出pair/triple/quadruple,使得他们的sum满足 一定条件(等于一个定值，接近一个定值，大于/小于一个定值)。题目问题的暴力解是O(n^2)/ O(n^3)/O(n^4)

解法分析

这样的题目其实类似一个背包问题，但是背包问题的解可能是任意长度的subset，而two sum问题 的区别在于给定subset的长度(2, 3, 4), 所以暴力解也就是polynomial级别的了。这种级别 的暴力解不是背包问题擅长优化的。所以我们会想到two sum类解法。同时，two sum问题其实有两种解法：

• HashMap，这样的解法一般适用于找满足条件pair的index，因为使用HashMap的话，我们就不用 sort；而一旦我们sort，我们就会丢失原来的index的信息。补救办法是用wrapper把index记录下来， 但是总的来看代码量会复杂不少。HashMap也可以解有duplicate的问题，我们还是把key存成 value, 把value存成a list of index，这样可以保留所有的pair。

• 相比之下，双指针更强大。使用two sum类双指针的第一步，就是去sort array，这样才能利用 和的单调性。而且因为two sum类双指针是对撞型，所以遇到A[i] + A[j] > A[k] 这种triple 不都是在等式一侧的情况，我们要使得在等式一侧的pair进行对撞，因为有了对撞才能减少重复 计算。另外，sort之后的two sum pointers也可以解决duplicate的问题。解决办法就是当我们找到一对pair比如 2和3相加等于target 5的时候，我们先去start++找到所有的2的count比如是2，然后end--找到所有的3的count比如是3。这样我们知道符合当前组合下符合条件的pair有2*3 = 6种。然后我们可以update start and end pointer使得我们不会再去遍历重复的duplicate。

题目

Two Sum

• Leetcode 1. Two Sum
• Leetcode 15. 3Sum
• Leetcode 16. 3Sum Closest
• Leetcode 259. 3Sum Smaller
• Leetcode 18. 4Sum