class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        for(int k = 0; k < nums.size(); k++){
            if(k > 0 && nums[k] == nums[k - 1])
                continue;
            int i = k + 1, j = nums.size() - 1;
            while(i < j){
                if(nums[i] + nums[j] == -nums[k]){
                    ans.push_back(vector<int>{nums[k],nums[i],nums[j]});
                    i++, j--;
                    //去重
                    while(i < j && nums[i] == nums[i - 1])
                        i++;
                    while(i < j && nums[j] == nums[j + 1])
                        j--;
                }
                // > 的话j左移
                else if(nums[i] + nums[j] > -nums[k]){
                    j--;
                }
                // < 的话i右移
                else{
                    i++;
                }
            }
            
        }
        return ans;
    }
};