18. 四数之和

18. 四数之和

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&&num[k]>=0) break; //你这个数都大于target了(前提是这个玩意儿是>0的)
        //对nums[k]去重复
        if(k>0&&nums[k]==nums[k-1]){
            continue;
        }
        for(int i = k+1;i<nums.size();i++){
            //2级剪枝处理
            if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0) break;
            //对nums[i]去重
            if(i>k+1&&nums[i]==nums[i-1]) continue;
            int left=i+1;
            int right=nums.size()-1;
            while(right>left){
                if((long)nums[k]+nums[i]+nums[left]+nums[right]>target) right--;
                else if((long)nums[k]+nums[i]+nums[left]+nums[right]<target) left++;
                else result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});
                while(right>left&&nums[right]==nums[right-1])right--;
                while(right>left&&nums[left]==nums[left+1]) left++;
                right--;
                left++;
            }
        }
    }
    return result;
}