class Solution {
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
// 创建vector<vector<int>> 类型的变量不赋值时，不会自动包含任何随机值，而是保持为空的状态
// 等价于 std::vector<std::vector<int>> res = {};
std::vector<std::vector<int>> res;
// 本题只要求返回vector元素，可排列vector。若要求返回下标，以下方法不可行
sort(nums.begin(), nums.end());
// if (nums[nums.size()-1] < 0) return res; 对所有数小于0的情形剪枝
for (int i=0; i<nums.size();i++){
// 错误 if (nums[i]>=0) 反例[0,0,0]
if (nums[i]>0) return res; // 剪枝
if (i>0 && nums[i] ==nums[i-1]) continue; // 对nums[i]去重一
int left = i+1, right = nums.size()-1; // 双指针
while(left < right){
if (nums[i]+nums[left]+nums[right]>0) right--;
else if (nums[i]+nums[left]+nums[right]<0) left++;
else {
//res.push_back(vector<int>{nums[i], nums[left], nums[right]});编译器会推断容器类型
res.push_back({nums[i], nums[left], nums[right]});
// 错误一 left<right不能丢
// if 只执行一次条件判断和操作，while 会重复执行条件判断和操作，直到条件不再满足。此处的while 类似上文去重一 for循环加if
while (left<right && nums[left]==nums[left+1]) left++; // 对nums[left]去重二
while (left<right && nums[right]==nums[right-1]) right--;// 对nums[right]去重三
// 错误二 去重后忘记移动
left++, right--;
}
}
}
return res;
}
};
// 索引nums[left+1]和nums[++left]的区别在于
// ++left等同left=left+1，比left+1多了赋值操作
// while 因为多次执行，上一循环left的变化会影响下一循环，nums[left+1]和nums[++left]不等价
// 但if执行一次 if(nums[left+1]) 和 if(nums[++left])等价，虽然出循环left值不同
while (left<right && nums[left]==nums[left+1]) left++;
while (left<right && nums[left]==nums[++left]) left++;
class Solution{
public:
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::vector<std::vector<int>> res;
std::set<int> set(nums.begin(), nums.end());
std::vector<int> newnums(set.begin(), set.end());
// 转成set会删除重复的数 反例{-1, -1, 2}
for (int i = 0; i < newnums.size(); i++){
if (newnums[i] > 0) return res;
int left = i+1, right = newnums.size()-1;
while (left < right){
if (newnums[i] + newnums[left] + newnums[right] < 0) left++;
else if (newnums[i] + newnums[left] + newnums[right] > 0) right--;
else {
res.push_back({newnums[i], newnums[left], newnums[right]});
left++, right--;
}
}
}
return res;
}
};