1. 3Sum
给定一个无序数组（可能存在重复元素），是否存在三个数之和为0，输出所有不重复的三元组。
e.g. 给定数组 [-1, 0, 1, 2, -1, -4]，
结果集为：
[
[-1, 0, 1],
[-1, -1, 2]
]
原理：
首先升序排序
----------------------------------------------------
^ ^ ^
| | |
| j k
i
j 往后扫，k 往前扫
三数和 < 0 就 j++，> 0 就 k--
直到 == 0 再取下一组
C++实现：
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = ; i < nums.size(); i++) {
// 控制i不重复，只指向一组重复数字的第一个
if (i > && nums[i] == nums[i-])
continue;
int j = i + , k = nums.size() - ;
while (j < k) {
if (nums[i] + nums[j] + nums[k] < ) {
j++;
} else if (nums[i] + nums[j] + nums[k] > ) {
k--;
} else {
result.push_back({nums[i], nums[j], nums[k]});
// 控制j不重复，只指向一组重复数字的第一个
while (j < k && nums[j] == nums[j+])
j++;
// 控制k不重复，只指向一组重复数字的最后一个
while (j < k && nums[k] == nums[k-])
k--;
j++;
k--;
}
}
}
return result;
} 第4行如果写 i < nums.size() - 2会报 Runtime Error 错，不知道为什么？
2. 3Sum Closest
给定一个无序数组（可能存在重复元素），是否存在三个数之和最接近给定数target，输出这三个数的和。（假设每条输入只有唯一答案）
e.g. 给定数组 [-1, 2, 1, -4]，target = 1
则最接近target的和为2 （-1 + 2 + 1 = 2）
C++实现：
int threeSumClosest(vector<int>& nums, int target) {
// 数组元素小于等于3个则直接返回数组和
if (nums.size() <= ) {
return accumulate(nums.begin(), nums.end(), );
}
int close = nums[] + nums[] + nums[];
sort(nums.begin(), nums.end());
for (int i = ; i < nums.size(); i++) {
if (i > && nums[i] == nums[i-])
continue;
int j = i + , k = nums.size() - ;
while (j < k) {
int current = nums[i] + nums[j] + nums[k];
if (abs(current - target) < abs(close - target)) {
close = current;
if (current == target) {
return current;
}
}
(current < target) ? j++ : k--;
}
}
return close;
}PS：
C++对应的Java代码
vector<vector<int>> List<List<Integer>>
sort(nums.begin(), nums.end()); Arrays.sort(nums)；
result.push_back({nums[i], nums[j], nums[k]}); result.add(Arrays.asList(nums[i], nums[j], nums[k]));
abs(n) Math.abs(n)
3. 4Sum
给定一个无序数组（可能存在重复元素），是否存在四个数之和为目标数target，输出所有不重复的四元组。
e.g. 给定数组[1, 0, -1, 0, -2, 2]，target = 0.
结果集为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
原理与 3 Sum 相似，首先升序排序，i 从第一个扫到最后，j 从 i + 1 扫到最后。
两个指针为 p 和 k ，p 往后扫，k 往前扫，四数和 < 0 就 p++，> 0 就 k--；直到 == 0 再取下一组 p 和 k。
C++实现：
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
if (n < ) return {};
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = ; i < n - ; i++) {
if (i > && nums[i] == nums[i - ]) continue;
// 提高效率，本轮能取的最小的和与本轮能取的最大的和
if (nums[i] + nums[i + ] + nums[i + ] + nums[i + ] > target) break;
if (nums[i] + nums[n - ] + nums[n - ] + nums[n - ] < target) continue;
for (int j = i + ; j < n - ; j++) {
if (j > i + && nums[j] == nums[j - ]) continue;
// 提高效率，本轮能取的最小的和与本轮能取的最大的和
if (nums[i] + nums[j] + nums[j + ] + nums[j + ] > target) break;
if (nums[i] + nums[j] + nums[n - ] + nums[n - ] < target) continue;
// 最后两个指针p和k在最内层while上面定义
// 如模仿三数和在上面定义k并在j循环体内控制条件写j < k会导致j扫不到最后
int p = j + , k = n - ;
while (p < k) {
if (nums[i] + nums[j] + nums[p] + nums[k] < target) p++;
else if (nums[i] + nums[j] + nums[p] + nums[k] > target) k--;
else {
result.push_back({nums[i], nums[j], nums[p], nums[k]});
while (p < k && nums[p] == nums[p + ]) p++;
while (p < k && nums[k] == nums[k - ]) k--;
p++;
k--;
}
}
}
}
return result;
}