我爱学算法之—— 感受双指针带来的快感（下）

星辰与你

发布于 2024-12-29 08:29:53

7100

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

前言

本篇文章继续来学习双指针算法；继续加油！！！

一、三数之和

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

题目解析

题目要求我们在一个给定的数组中，找到和等于0的三元组；但是呢有一些要求

首先，这三元组中的元素是给定数组中的不同元素
其次，找到的三元组不能够重复

算法分析

暴力枚举+set去重

首先，看到题目第一想到的是暴力枚举，枚举出所有的三元组，找到和为0的，然后再进行去重操作。

利用双指针优化

当然，枚举所有三元组这样解法，时间复杂度为O(n^3)；而且去重操作也不简单，现在来优化一下。

我们这里借用两数之和中利用双指针算法找和为target的思路；依次固定（从左到右）给定数组中的数字i，然后利用双指针算法，在其右边区间内找到和为-i的两个数，找到返回即可。

细节处理

去重：对于去重操作，这里也不使用set去重（代价有些大）；直接让数组有序，在遍历数组时就直接跳过重复元素。
查找的三元组完全：对与这个问题，我们在利用双指针算法找到满足要求的数之后，让双指针继续遍历而不是直接结束即可。

过程分析

代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        //让数组有序
        sort(nums.begin(),nums.end());
        int n = nums.size();
        for(int i=0;i< n-2 &&nums[i]<=0;)
        {
            int left = i+1,right = n-1;
            int 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[i],nums[left++],nums[right--]});
                while(left<right && nums[left] == nums[left-1])
                    left++;
                while(left<right && nums[right] == nums[right+1])
                    right--;
                }
            }
            i++;
            while(i<n-2 && nums[i] == nums[i-1])
                i++;
        }
        return ret;
    }
};

部分代码解释：

首先，固定一个数的循环中，没有在for循环中执行i++是因为，在跳过重复元素的时候，已经指向完++了。
其次，双指针算法找到满足条件的元素后，没有直接跳出，而是跳过重复元素继续遍历。

二、四数之和

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

题目解析

题目要求我们在给定数组中，找到和为target的四元组。

首先，四元组中的四个元素不能重复；
其次，四元组不能重复

算法分析

思路：

首先，肯定是暴力枚举+去重；（不多说）

在其上进行优化；我们可以故技重施，借用一下三数之和的思想，来解决

从左到右固定一个数，在其右边区间寻找三数之和为target-a的（a为固定的数）
寻找三叔之和，从左到右固定一个数，在其右边区间寻找两数之和为target-a-b（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();
        for(int i=0;i<n;)
        {
            for(int j = i+1;j<n;)
            {
                long long x = (long long)target - nums[i] - nums[j];
                int left=j+1,right= n-1;
                while(left < right)
                {
                    int sum = nums[left] + nums[right];
                    if(sum > x)
                        right--;
                    else if(sum < x)
                        left++;
                    else
                    {
                        ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});
                        while(left < right && nums[left] == nums[left - 1])
                            left++;
                        while(left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                ++j;
                while(j<n && nums[j] == nums[j - 1])
                    ++j;
            }
            ++i;
            while(i < n&& nums[i] == nums[i - 1])
            ++i;
        }
        return ret;
    }

};