Sum集合

1. 3 sum
2. 3 sum closest
3. 3 sum smaller
4. 4 sum
5. 2 Sum
6. 2 Sum II

tip: 如果组合不可以重复的话，要记得skip over duplicates

1. 3 Sum

arrays.sort + 一个定点 + 2 pointers

Time: O(n^2)

因为要求3个element 组成的list不可以相同，所以，For loop需要检测当前定点是否和前一个定点的值相同。而且，移动Pointers的时候也要跳过相同的元素。

we can iterate over each number and inside the loop, solve the sub-problem as 2sum. To calculate the time complexity, sorting is O(NlogN), the outside loop is O(N) and the inside 2sum is O(N). Therefore, the overall time complexity is O(N^2) and space complexity is O(1).

2. 3 Sum Closest

arrays.sort + 一个定点 + 2 pointers

O(n^2) running time.

3. 3 Sum Smaller

count += (right - left)

如果 sum < target ，i 和 left 不动，介于 left 和 right (包括 right) 之间的所有元素 sum 也一定小于 target 的单调性。如果 sum < target， 则left++， 测试下一组组合。如果 sum > target，right--。

O(n^2)

类似题 Valid Triangle Number

4. 4 Sum

2 for loop + two pointers + skip same elements

O(n^3)

基本上就是两个for loop和两个指针，但是在for loop一开始的地方可以优化下时间。

在第一层for loop：

1. 如果num[i] + 最后面三个最大的数字 < target的话，说明num[i] 太小了，continue;

2. 如果num[i] + 紧跟着的三个数字 > target的话，说明num[i] 太大了，break;

3. 如果i > 0 && num[i] > num[i - 1]的话，skip over duplicates。因为题目中说不可以有重复的quadruplets。

在第二层也是类似的：

1. 如果num[i] + num[k] + 最后面2个最大的数字 < target的话，说明num[k] 太小了，continue;

2. 如果num[i] + num[k] + 紧跟着的2个数字 > target的话，说明num[k] 太大了，break;

3. 如果k > i + 1 && num[k] > num[k - 1]的话，skip over duplicates。因为题目中说不可以有重复的quadruplets。