算法入门：专题攻克一---双指针4（三数之和,四数之和）强推好题，极其锻炼算法思维

三数之和

三数之和

1. 题目分析：

取三元组中的三个数，num[i], num[j], num[k], i!=j, i != k; j != k ,也就是说一次取到的三个数不可以是相同位置的，三个数的位置各不相同。同时也满足三个数的相加等于0。最后还得是不同的组合（去重操作）。 这里给一个数组，便于演示： 【 -4 -4 -1 0 0 0 1 1 4 4 5 6】

1. 算法原理：

解法一：先排序+暴力枚举+利用set去重 将所有符合要求的元素都枚举出来，然后再根据相同的元素进行排查，这里提出优化，我们可以将数组先进行排序，然后再选用暴力枚举的方法。先排序这样数据就不会显得那么凌乱。最后利用set去重。

解法二：排序+双指针 排完序之后，数组就是有序数组，这里我们也进行相对应的排序， 【 -4 -4 -1 0 0 0 1 1 4 4 5 6】

然后使用双指针来写这个题。先固定一个i,每一趟都要固定一个i,这个i我们从左到右依次向后走，这里先来说第一趟该怎么走，定义一个固定的i，还要定义一个left在索引为1的位置，从前往后走，right在索引为n-1的位置，从后往前走，当left<right的时候，left和right按照各自的轨道走，因为最终返回三元组必须加起来等于0，已经有了一个已知的i ，所以num[left]+num[right]相加要等于-num[i] 。

考虑去重的问题：

1.left和right在找到一种结果之后要跳过重复的元素，而且每走一趟left和right，i 的位置也要向后挪动一位，同时也要跳过重复的元素。避免越界。

1. 这里我们尝试将文字理解转换为代码：

首先题目中需要做到最后返回的三元组是不重复的数字组合，所以这里定义一个vector<vector<int>>ret，用ret来封装最后的结果，将找到的所有符合要求的三元组都push_back进去。

接着要进行排序，将数组拍成一个有序的数组，便于后续的操作，sort(nums.begin().nums.end());

然后排好序之后利用双指针算法来解题；首先要固定一个数字 i ，这个数字将作为三元组的第一个已知数字，其余两个数字相加的和sum必须等于这个固定数字的相反数，因为三个数字相加最终要等于0； for(int i=0;i<nums.size(); i++) 然后定义left在i的下一个位置，right在索引为nums.size()-1的位置，每趟都要求left和right两个指针寻找符合要求的数字，定义一个target来表示nums[i]的相反数。

当left向后遍历，right向前遍历，他们的循环结束是left>=right;接着进行判断，

如果sum >target,右边的数字太大了，需要向前right--; 如果sum<target,左边的数字太小了，需要向后left++; 还要一种情况就是符合我们的要求，刚好sum=target,此时可以将nums[left],nums[right],nums[i]压栈存入ret中。

现在来到很关键的一步：去重问题，sum=target之后，要拿到left的下一个位置，与right的前一个位置，此时left++,right--;要是拿到的left跟之前的是相等的，那么在此时，nums[i]和num[left]的值跟刚才sum过的是一样的，可想而知，这个数组就会造成冗余，所以我们在取left和right的位置的时候不可以取刚才拿过的数字，否则达不到题目的要求。

那么怎么去重？？？ 如果此时的nums[left]等于前一个拿过的nums[left-1]，此时就让left向后挪动一个位置，left++,前提条件是left<right,不会构成越界。 如果此时的nums[right]等于前一个拿过的nums[right+1]，此时就让right向前挪动一个位置，right--,前提条件是left<right,不会构成越界。

第一趟就完美结束啦！ 不过，固定数字 i 也有可能会造成重复三元组，所以先让i++到下一个位置判断，如果此时的nums[i]等于前一个操作过的nums[i-1] ,此时i++,一直加到合适的位置，用while循环，前提条件不可以越界，i< nums.size() 所以修改之前定义的for循环for(int i=0;i<nums.size(); )

最后我们返回return ret即可，就可以拿到最后的结果。

1. 上代码！

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //1.排序
        sort(nums.begin(),nums.end());
        vector<vector<int>> ret;//封装所有符合条件的三元组

        int n=nums.size();
        for(int i=0;i<n;)
        {
            if(nums[i]>0) break;//优化，不写不影响做题
            int left=1+i,right=n-1,target=-nums[i];
            while(left<right)
            {
                int sum=nums[left]+nums[right];
                if(sum>target) right--;
                else if(sum<target) left++;
                else{
                    ret.push_back({nums[left],nums[right],nums[i]});
                    left++,right--;

                    //去重left和right
                    while(nums[left]==nums[left-1]&&left<right) left++;
                    while(nums[right]==nums[right+1]&&left<right) right--;
                }
            }//去重i
            i++;
            while(i<n && nums[i]==nums[i-1] ) i++;
        }
        return ret;
    }
    
};

四数之和

四数之和

1. 题目解析：

这道题跟三数之和是相当类似的。

1. 算法原理：

解法一：排序+暴力枚举+利用set去重 解法二： 先排序，再利用双指针

1.依次固定一个数a； 2.在a后面的区间内，利用“三数之和”找到三个数，使得这三个数的和等于target-num[a]即可。 再固定一个数b，在b后面的区间内利用双指针找到两个数，使得这两个数的和等于target-num[a]-num[b]即可。 处理细节问题： 1.不重复：left和right都要跳过重复的元素，a和b都要跳过重复的元素。

大体上还是三数之和的思想，差不多的题目，在代码的编写过程中应该会有两层for循环，这 里来写代码。

1. 上代码！

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

总结：

总的来说这两道题目具有非常强的相似性。

三数之和，每一趟只固定一个数字i,然后left,right区间里的两个数字要等于 num[i]的相反数，最后找出三元组。 注意讨论去重越界问题。left和right的去重，不能选择重复元素；i要去重，也不能选择重复元素。

四数之和，每一趟固定一个数字 a,然后剩下的区间中做三数之和的问题， 在剩下区间中固定一个b，然后在索引为2的元素到索引为nums.size()-1这段区间中寻找两个数字，left和right相加要等于target-nums[a]-nums[b] ,最后找出四个数字。 注意讨论去重越界问题，left和right的去重，不能选择重复元素，这是一重去重；b要去重，不能选择重复元素，二重去重；a要去重，不能选择重复元素，这是三重去重。

可以类似为同一道题。