2 sum, 3 sum, k sum及相关
Question List
- 2 sum
- 2 sum data structure
- 3 sum
- 3 sum closest
- 3 sum smaller
- 4 sum
- k sum
主要思想
- 2 sum可以hashtable
O(n)
- 比较general的解法是2 pointers
O(nlogn), 因为要先sort
4 sum -> 3 sum -> 2 sum
3 sum 是O(n^2) = O(nlogn) + O(n * n), 并不是O(logn * n ^ 2)这个要注意！
衍生类的题目比如3 sum closest, 3 sum smaller这种用2 pointer的方法比较好做
k sum 可以写成recursive的方式