给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
借着这道题，我们再重温一下拿到题目之后的思考过程。首先还是老规矩，看完题意之后首先来看看数据范围。
数据范围当中隐藏的信息很多，还可以用来大致确定一下正确解答的复杂度，有很强的提示性。所以千万不要忽略，一定要仔细查看。
这道题当中数据的范围并不大，最多只有3000个数，每个数的范围是1e5，即使是三个数相加也不会超过int的范围，相对比较安全。其次最多只有3000个数，意味着$O(n^2)$甚至是$O(n^2\log n)$都是可以接受的，相对来说，复杂度卡的不是非常死。
分析完了复杂度之后，我们可以尝试一下暴力的方法，看看暴力求解有没有什么问题，有哪些问题。绝大多数的问题暴力求解是不行的，但这并不是白费功夫。思考完了暴力解法之后，我们就能找到题目的难点。
也就是说第二个步骤是找到难点，几乎所有的算法题都是有难点的，这些难点基本上都是出题人刻意设置的。所以当我们不能或者是很难直接求解找到突破口的时候，不妨尝试一下难点分析，即想一想这题究竟难在哪里，真正困难的点在哪里。
以本题为例，我们要找到三个数，使得它们的和为0，并且要找出所有的组合。对于找所有解的问题来说，它的前提就是我们要能枚举所有可能构成解的可能性。在这道题当中，三个数的组合数量是$O(n^3)$的量级，这是无法接受的。
那么难点也就找到了：我们要枚举的可能性太多，会导致复杂度无法接受。所以我们要做的就是想办法既能够枚举所有的可能性，又保证复杂度不会超过限制。
从理论上看，n个数当中找3个，无论如何也有$n^3$的量级，看似是无解的。但是我们仔细分析题目，可以找到突破口，这个突破口就是三个数和为0。既然三个数和为0，那么就对这三个数的组成有了一定的限制。很明显，这三个数不能全大于0，也不能全小于0。除非全为0，否则必须有正有负。进而我们可以想到，我们可以枚举其中一个值，在此基础上寻找另外两个值。
假设a+b+c=0，我们不妨设$a \le b \le c$。那么我们只需要枚举a，在此基础上，在大于等于a的部分当中寻找b和c的组合。由于$a\le b \le c$，那么a一定小于等于0。所以我们只需要在小于等于0的范围内枚举a，在大于等于a的范围内枚举b和c即可，这样就去掉了大部分无谓的组合，减小了搜索空间，提升了算法的效率。
到这里我们又很容易发现，无论是要在小于等于0的范围内枚举a，还是要在大于等于a的范围内枚举b和c，我们都需要数组元素有序。所以我们可以先对数组排序，使得数组中元素有序，接着在小于等于0的范围内枚举a，在a的右侧枚举b和c，寻找b+c=-a的组合。寻找b和c的过程，本质上是一个寻找两数和的问题。对于两数和的问题，我们已经比较熟悉了，我们当然可以使用map来维护，但由于元素已经有序了，我们也可以使用双指针直接来寻找。
完整代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
// 数组排序
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
// a+b+c=0, a <= b <= c, 枚举a
for(int i = 0; i < n-2; i++) {
// a大于0跳出
if (nums[i] > 0) break;
// 剪枝，去除重复搜索
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1;
int r = n-1;
while (l < r) {
// target = a + b + c, 根据target和0的关系决定是右移l或左移r
int target = nums[i] + nums[l] + nums[r];
if (target == 0) {
vector<int> cur {nums[i], nums[l], nums[r]};
ret.push_back(cur);
l++; r--;
// 跳过重复
while (l < r && nums[l] == nums[l-1]) l++;
// 跳过重复
while (l < r && nums[r] == nums[r+1]) r--;
}else if (target > 0) r--;
else l++;
}
}
return ret;
}
};