算法——双指针（day4)

15.三数之和

15. 三数之和 - 力扣（LeetCode） 

题目解析：

这道题目说是三数之和，其实这和我们之前做过的两数之和是一个规律的~无非就是我们需要实时改动target的值。先排好序，然后固定一个数取其负值作target，然后我们再从除固定数以外的范围内寻找两数之和为target的数，这样再与固定数相加就得到0了，形成三元数组。

算法解析：

这就是两数和的核心图解，唯一区别就是我们的target值是随着固定数的变化而发生改变的~

废话不多说，本题的难点就在于去重以及去重时的越界问题。因为按照题目规定类似于

【-1，0，-1】与【-1，-1，0】这种会算重复项只能取其一，而这也是我们优先选择排序的原因，在排行序后二者就变为【-1，-1，0】，更容易去重。

去重分两个阶段，一是【left,right】范围之间的去重，另一个是固定数first遍历数组的去重。

所以我们给出的去重方案就是观察移动前后的数值是否相同，如果相同那就再移动一位，直到不同为止。不过这样也引发了新的问题：越界~

 

我们发现left与right的选取是需要在【left,rigtht】这个界限里面的，所以只需要加上一层条件即可（left<right)~

 固定数first同理：

代码： 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int first = 0;
        while (first <= n - 3)
        {
            //小优化
            if (nums[first] > 0) break;
            int left = first + 1;
            int right = n - 1;
            int target = -nums[first];
            //一轮比较
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target)
                {
                    --right;
                }
                else if (sum < target)
                {
                    ++left;
                }
                else
                {
                    ret.push_back({ nums[first],nums[left],nums[right] });
                    right--;
                    left++;
                    //left与right去重
                    while (left < right && nums[right + 1] == nums[right])
                    {
                        right--;
                    }
                    while (left < right && nums[left - 1] == nums[left])
                    {
                        left++;
                    }
                }

            }
            //固定数去重
            first++;
            while (first < n && nums[first - 1] == nums[first])
            {
                first++;
            }

        }
        return ret;
    }
};

18.四数之和

18. 四数之和 - 力扣（LeetCode）

题目解析：

四数之和别看多了一个数，其实和三数之和还是同一个模板，没有本质区别

算法解析：

 

找四数之和我们可以先拆分成固定数a与三数之和，那么三数之和的值就得为target-a。这样a与三数之和才相加才可以变为target，而在三数之和中就得拆分成固定数b与两数之和，那么两数之和的值就得为target-a-b，这样才能与b相加得到target-a。

所以只要在三数之和的代码中把控好target-a-b的值就行了，除此之外再多加一个对固定数a的去重就好了~

 代码：

在三数之和外套一层固定数a的循环以及去重复，另外改变目标值t变为target-a-b就差不多了。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int a = 0;
        //固定数a
        while (a <= n - 4)
        {
            //固定数b
            int b = a + 1;
            while (b <= n - 3)
            {
                int left = b + 1;
                int right = n - 1;
                //防止数据溢出强转类型
                long long t = (long long)target - nums[b] - nums[a];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > t)
                    {
                        --right;
                    }
                    else if (sum < t)
                    {
                        ++left;
                    }
                    else
                    {
                        ret.push_back({ nums[a],nums[b],nums[left],nums[right] });
                        right--;
                        left++;
                        //一级去重复
                        while (left < right && nums[right + 1] == nums[right])
                        {
                            right--;
                        }
                        while (left < right && nums[left - 1] == nums[left])
                        {
                            left++;
                        }
                    }

                }
                //二级去重
                b++;
                while (b < n && nums[b - 1] == nums[b])
                {
                    b++;
                }

            }
            //三级去重
            a++;
            while (a < n && nums[a - 1] == nums[a])
            {
                a++;
            }

        }
        return ret;
    }
};