class Solution {
public:
/* 暴力搜索法
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
for (int k = j + 1; k < nums.size(); k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
vector<int> tmp{nums[i], nums[j], nums[k]};
sort(tmp.begin(), tmp.end());
int n = 0;
for (; n < ret.size(); n++) {
if (tmp == ret[n]) {
break;
}
}
if (n == ret.size()) {
ret.push_back(tmp);
}
}
}
}
}
return ret;
}
*/
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先排序，后面好遍历
int size = nums.size();
vector<vector<int>> ret;
if (size < 3) { // 数组元素少于3
return ret;
}
for (int i = 0; i < size; i++) { // 遍历开始
if (i > 0 && nums[i] == nums[i-1]) { // 跟前一个元素相同，跳过
continue;
}
if (nums[i] > 0) { // 最小数字已经大于0，因为是排序好的，那后面的肯定也大于0，就没有必要继续遍历了
return ret;
}
int left = i + 1; // 双指针的左侧位置
int right = size - 1; // 双指针的右侧位置
while (left < right) { // 开始双指针相对移动
if (nums[i] + nums[left] + nums[right] < 0) { // 和<0，意味着要增大其中一个数字，所以移动左侧指针（向右）
left++;
} else if (nums[i] + nums[left] + nums[right] > 0) { // 和>0，则要减小一个数字，所以移动右侧指针（向左）
right--;
} else { // 找到和=0的三元组
ret.push_back({nums[i], nums[left], nums[right]});
left++; // 继续下一轮
right--; // 继续
// 这里是关键点，要跳过相同的三元组，我之前写的是跟left+1比较，所以一直解答错误，
// 如果是left+1，因为上面已经left++了，所以就变成了下一个和下下一个比较，而不是当前和下一个比较了，下面的right也是一样，
// 除非把left++和right--移到这两次遍历的下面，那样就可以用left和left+1比较了。
while (left < right && nums[left] == nums[left-1]) left++;
while (left < right && nums[right] == nums[right+1]) right--;
}
}
}
return ret;
}
};