twoSum
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标.
nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。
vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
// nums 数组必须有序
sort(nums.begin(), nums.end());
int lo = 0, hi = nums.size() - 1;
vector<vector<int>> res;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
// 跳过相同元素，避免重复
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
// 跳过相同元素，避免重复
while (lo < hi && nums[hi] == right) hi--;
} else {
res.push_back({left, right});
// 跳过相同元素，避免重复
while (lo < hi && nums[lo] == left) lo++;
// 跳过相同元素，避免重复
while (lo < hi && nums[hi] == right) hi--;
}
}
return res;
}
3Sum
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = target ？请你找出所有和为 target 且不重复的三元组。
分析：
现在我们想找和为 target 的三个数字，那么对于第一个数字，可能是什么？nums 中的每一个元素 nums[i] 都有可能！
那么，确定了第一个数字之后，剩下的两个数字可以是什么呢？其实就是和为 target - nums[i] 的两个数字呗，那不就是 twoSum 函数解决的问题么。
/* 从 nums[start] 开始，计算有序数组
* nums 中所有和为 target 的二元组 */
vector<vector<int>> twoSumTarget(
vector<int>& nums, int start, int target) {
// 左指针改为从 start 开始，其他不变
int lo = start, hi = nums.size() - 1;
vector<vector<int>> res;
while (lo < hi) {
...
}
return res;
}
/* 计算数组 nums 中所有和为 target 的三元组 */
vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
// 数组得排个序
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> res;
// 穷举 threeSum 的第一个数
for (int i = 0; i < n; i++) {
// 对 target - nums[i] 计算 twoSum
vector<vector<int>>
tuples = twoSumTarget(nums, i + 1, target - nums[i]);
// 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
for (vector<int>& tuple : tuples) {
tuple.push_back(nums[i]);
res.push_back(tuple);
}
// 跳过第一个数字重复的情况，否则会出现重复结果
while (i < n - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
关键点在于，不能让第一个数重复，至于后面的两个数，我们复用的 twoSum 函数会保证它们不重复。所以代码中必须用一个 while 循环来保证 3Sum 中第一个元素不重复。
4Sum
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
分析：
都到这份上了，4Sum 完全就可以用相同的思路：穷举第一个数字，然后调用 3Sum 函数计算剩下三个数，最后组合出和为 target 的四元组。
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 数组需要排序
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> res;
// 穷举 fourSum 的第一个数
for (int i = 0; i < n; i++) {
// 对 target - nums[i] 计算 threeSum
vector<vector<int>>
triples = threeSumTarget(nums, i + 1, target - nums[i]);
// 如果存在满足条件的三元组，再加上 nums[i] 就是结果四元组
for (vector<int>& triple : triples) {
triple.push_back(nums[i]);
res.push_back(triple);
}
// fourSum 的第一个数不能重复
while (i < n - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
/* 从 nums[start] 开始，计算有序数组
* nums 中所有和为 target 的三元组 */
vector<vector<int>>
threeSumTarget(vector<int>& nums, int start, int target) {
int n = nums.size();
vector<vector<int>> res;
// i 从 start 开始穷举，其他都不变
for (int i = start; i < n; i++) {
...
}
return res;
}
nSum
那么，如果我让你求 100Sum 问题，怎么办呢？其实我们可以观察上面这些解法，统一出一个 nSum 函数：
/* 注意：调用这个函数之前一定要先给 nums 排序 */
vector<vector<int>> nSumTarget(
vector<int>& nums, int n, int start, int target) {
int sz = nums.size();
vector<vector<int>> res;
// 至少是 2Sum，且数组大小不应该小于 n
if (n < 2 || sz < n) return res;
// 2Sum 是 base case
if (n == 2) {
// 双指针那一套操作
int lo = start, hi = sz - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.push_back({left, right});
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 时，递归计算 (n-1)Sum 的结果
for (int i = start; i < sz; i++) {
vector<vector<int>>
sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (vector<int>& arr : sub) {
// (n-1)Sum 加上 nums[i] 就是 nSum
arr.push_back(nums[i]);
res.push_back(arr);
}
while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
}