[15]三数之和

//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
//复的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [-1,0,1,2,-1,-4]
//输出：[[-1,-1,2],[-1,0,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：nums = [0]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 3000 
// -105 <= nums[i] <= 105 
// 
// Related Topics 数组 双指针 
// 👍 2981 👎 0

/*
* 15 三数之和
* 2021-02-22 09:01:42
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution2 {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> ans;

        sort(nums.begin(), nums.end());
        if(nums.size() < 3 || nums.front() > 0 || nums.back() < 0) return {};
        // nums has been sorted
        for(int k = 0;k < nums.size() - 2;k++){
            if(nums[k] > 0) break;
            int target = 0 - nums[k], i = k + 1, j = nums.size() - 1;
            while(i < j){
                if(nums[i] + nums[j] == target){
                    ans.insert({nums[k], nums[i], nums[j]});
                    while(i < j && nums[i] == nums[i+1]) i++;
                    while(i < j && nums[j] == nums[j-1]) j--;
                    ++i, --j;
                }else if(nums[i] + nums[j] < target){
                    ++i;
                }else
                    --j;
            }
        }
        return vector<vector<int>>(ans.begin(), ans.end());
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> ans;

        sort(nums.begin(), nums.end());
        if(nums.size() < 3 || nums.front() > 0 || nums.back() < 0) return {};
        // nums has been sorted
        for(int k = 0;k < nums.size() - 2;k++){
            if(nums[k] > 0) break; //剪枝
            if (k > 0 && nums[k] == nums[k - 1]) continue; // 判重
            int target = 0 - nums[k], i = k + 1, j = nums.size() - 1;
            while(i < j){
                if(nums[i] + nums[j] == target){
                    ans.push_back({nums[k], nums[i], nums[j]});
                    while(i < j && nums[i] == nums[i+1]) i++;
                    while(i < j && nums[j] == nums[j-1]) j--;
                    ++i, --j;
                }else if(nums[i] + nums[j] < target){
                    ++i;
                }else
                    --j;
            }
        }
        return ans;
    }
};
//leetcode submit region end(Prohibit modification and deletion)