15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
16. 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。示例 2：
输入：nums = [0,0,0], target = 1
输出：0提示：
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104
解答
这两道题目求解思路很相似，只是第一个题目需要返回所有满足求和条件的组合，第二个题目返回最接近target的sum值。
方法一：排序 + 双指针
题目要求找到与目标值 $target$ 最接近的三元组，这里的「最接近」即为差值的绝对值最小。我们可以考虑直接使用三重循环枚举三元组，找出与目标值最接近的作为答案，时间复杂度为 $O(N^3)$。然而本题的 $N$ 最大为 $1000$，会超出时间限制。
那么如何进行优化呢？我们首先考虑枚举第一个元素 $a$，对于剩下的两个元素 $b$ 和 $c$，我们希望它们的和最接近 $target-a$。对于 $b$ 和 $c$，如果它们在原数组中枚举的范围（既包括下标的范围，也包括元素值的范围）没有任何规律可言，那么我们还是只能使用两重循环来枚举所有的可能情况。因此，我们可以考虑对整个数组进行升序排序，这样一来：
假设数组的长度为 $N$，我们先枚举 $a$，它在数组中的位置为 $i$；
为了防止重复枚举，我们在位置$[i+1,n)$的范围内枚举 $b$ 和 $c$。
当我们知道了 $b$ 和 $c$ 可以枚举的下标范围，并且知道这一范围对应的数组元素是有序（升序）的，那么我们是否可以对枚举的过程进行优化呢？
答案是可以的。借助双指针，我们就可以对枚举的过程进行优化。我们用 $p_b$和 $p_c$分别表示指向 $b$ 和 $c$ 的指针，初始时，$p_b$指向位置$i+1$，即左边界；$p_c$指向位置 $n-1$，即右边界。在每一步枚举的过程中，我们用 $a+b+c$ 来更新答案，并且：
如果 $a+b+c \ge target$，那么就将 $p_c$向左移动一个位置；
如果 $a+b+c \le target$，那么就将 $p_b$向右移动一个位置。
这是为什么呢？我们对 $a+b+c \ge target$ 的情况进行一个详细的分析：
如果 $a+b+c \ge target$，并且我们知道 $p_b$到 $p_c$这个范围内的所有数是按照升序排序的，那么如果 $p_c$不变而 $p_b$向右移动，那么 $a+b+c$ 的值就会不断地增加，显然就不会成为最接近 $target$ 的值了。因此，我们可以知道在固定了 $p_c$的情况下，此时的 $p_b$就可以得到一个最接近 $target$ 的值，那么我们以后就不用再考虑 $p_c$了，就可以将 $p_c$向左移动一个位置。
同样地，在 $a+b+c \le target$ 时：
如果 $a+b+c \le target$，并且我们知道 $p_b$到 $p_c$这个范围内的所有数是按照升序排序的，那么如果 $p_b$不变而 $p_c$向左移动，那么 $a+b+c$ 的值就会不断地减小，显然就不会成为最接近 $target$ 的值了。因此，我们可以知道在固定了 $p_b$的情况下，此时的 $p_c$就可以得到一个最接近 $target$ 的值，那么我们以后就不用再考虑 $p_b$了，就可以将 $p_b$向右移动一个位置。
实际上，$p_b$和 $p_c$就表示了我们当前可以选择的数的范围，而每一次枚举的过程中，我们尝试边界上的两个元素，根据它们与 $target$ 的值的关系，选择「抛弃」左边界的元素还是右边界的元素，从而减少了枚举的范围。这种思路与 11. 盛最多水的容器 中的双指针解法也是类似的。
小优化
本题也有一些可以减少运行时间（但不会减少时间复杂度）的小优化。当我们枚举到恰好等于 $target$ 的 $a+b+c$ 时，可以直接返回 $target$ 作为答案，因为不会有再比这个更接近的值了。
另一个优化与 15. 三数之和的官方题解 中提到的类似。当我们枚举 $a,b,c$中任意元素并移动指针时，可以直接将其移动到下一个与这次枚举到的不相同的元素，减少枚举的次数。
15题C++实现：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
//对数组进行排序
sort(nums.begin(), nums.end());
int n = nums.size();
//枚举a
for (int i = 0; i < n; ++i) {
//保证和上一次枚举的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int target = -nums[i];
//使用双指针枚举b和c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[j] + nums[k];
// 如果和为target则直接返回答案
if (sum == target) {
result.push_back({nums[i], nums[j], nums[k]});
}
if (sum > target) {
//如果和大于target， 移动c对应的指针
int k0 = k - 1;
//移动到下一个不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
//如果和小于target, 移动b对应的指针
int j0 = j + 1;
//移动到下一个不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return result;
}
};16题C++实现：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
//对数组进行排序
sort(nums.begin(), nums.end());
int n = nums.size();
int best = 1e7;// initial
//根据差值的绝对值来更新答案
/*
auto toNumber = [&](string const& s) -> unsigned {
...
}
[]：定义匿名函数
[&]：以引用形式捕获所有外部变量，也就是外部变量均可用
(string const &s) ：匿名函数的参数
->：定义匿名函数
unsigned：函数返回值类型
{...}：函数实现体
*/
auto update = [&](int cur) {
if (abs(cur - target) < abs(best - target)) {
best = cur;
}
};
//枚举 a
for (int i = 0; i < n; ++i) {
//保证和上一次枚举的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
//使用双指针枚举b和c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果和为target则直接返回答案
if (sum == target) {
return target;
}
update(sum);
if (sum > target) {
//如果和大于target， 移动c对应的指针
int k0 = k - 1;
//移动到下一个不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
//如果和小于target, 移动b对应的指针
int j0 = j + 1;
//移动到下一个不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
};