三数之和

题目链接：三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

方法：二分查找

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        for (int i = 0;i < nums.size()-2;i++) {
            int x = nums[i];
            int n = nums.size();
            if (i && x == nums[i-1]) continue;
            if (x + nums[i+1] + nums[i+2] > 0) break;
            if (x + nums[n-1] + nums[n-2] < 0) continue;
            int j = i+1,k = n-1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) {
                    k--;
                }else if (s < 0) {
                    j++;
                }else {
                    ans.push_back({x,nums[j],nums[k]});
                    for (j++;j < k && nums[j] == nums[j-1];j++);
                    for (k--;k > j && nums[k] == nums[k+1];k--);
                }
            }
        }
        return ans;
    }
};