1.题目

题目分析：

给一个数组，在里面找到四个数字，满足四个数字之和等于给的特定值，四数之和可以拆分成三数之和，再继续拆分成二数之和，由简化繁。

2.算法原理

通过排序加双指针

1.依次固定一个数

2.在第一个固定的数后面的区间内，利用三数之和找到三个数，使这三个数的和等于target-第一个固定的数

3.三数之和，固定第二个数，然后再剩下的区间内找到俩个数字，使和等于target-第一个固定的数字-第二个固定的数字

注意：要去重，不能漏。

3.代码实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> arr;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();)
        {
            int target1=(target-nums[i]);
            for(int j=i+1;j<nums.size();)
            {
                
                long long target2=((long long)target1-nums[j]);
                int left=j+1,right=nums.size()-1;
                while(left<right)
                {
                    int sum=nums[right]+nums[left];
                    if(sum>target2) right--;
                    else if(sum<target2) left++;
                    else
                    {
                        arr.push_back({nums[i],nums[j],nums[left],nums[right]});
                        left++,right--;
                        while(left<right&&nums[left]==nums[left-1]) left++;
                        while(left<right&&nums[right]==nums[right+1]) right--;
                    }
                }
                j++;
                while(j<nums.size()&&nums[j]==nums[j-1]) j++;
            }
            i++;
            while(i<nums.size()&&nums[i]==nums[i-1]) i++;
        }
        return arr;
    }
};