四数之和

题目：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，

使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        for(int k=0;k<nums.size();k++)
        {
            if(nums[k]>target && nums[k]>=0)//第一次剪枝
            {
                break;
            }
            if(k>0 && nums[k]==nums[k-1])//去重，位置不能颠倒
            {
                continue;
            }

            for(int i=k+1;i<nums.size();i++)
            {
                if(nums[k]+nums[i]>target && nums[k]+nums[i]>=0)//第二次剪枝
                {
                    break;
                }

                if(nums[i]==nums[i-1]&&i>k+1)//去重
                {
                    continue;
                }

                int left=i+1;
                int right=nums.size()-1;

                while(right>left){
                int sum=nums[k]+nums[i]+nums[left]+nums[right];

                if(sum>target){
                right--;
                }
                else if(sum<target)
                {
                left++;
                }
                else{
                result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});
                while(right>left&&nums[left]==nums[left+1])left++;//去重
                while(right>left&&nums[right]==nums[right-1])right--;
                
                left++;
                right--;
                }
                }


            }
            
        }
        return result;
    }
};