初识算法 · 双指针(3)

时间:2024-10-04 07:44:48

目录

前言:

和为s的两数之和

题目解析:

​编辑

算法原理:

算法编写:

三数之和

题目解析

算法原理

算法编写


前言:

本文通过介绍和为S的两数之和,以及三数之和,对双指针算法进行深一步的了解,介绍该算法博主使用三部曲,第一步对题目进行分析,里面会夹杂着暴力解法的问题,第二步对于算法原理进行分析,第三步则是对算法进行编写,最后分析时间复杂度,可能会分析空间复杂度。

题目的链接为:

LCR 179. 查找总价格为目标值的两个商品 - 力扣(LeetCode)

15. 三数之和 - 力扣(LeetCode)

那么话不多说,进入正题吧!


和为s的两数之和

题目解析:

该题目的要求是找到两个数,这两个数相加的和是等于target的。题中也有个很重要的条件,按照升序记录于数组中,这个升序是十分关键的。我们直接探讨暴力解法,即将所有的两数之和举例出来,第一次相等就返回即可,如果运气差点,就需要遍历完整个数组两次,即两个for循环,此时的时间复杂度为O(N^2),这是暴力解法,是比较容易想出来的:

for (int i = 0; i < price.size();i++)
{
	for (int j = 0;j < price.size();j++)
	{
		//判断是否满足条件
	}
}

当然了,如果使用暴力解法,那么我们对题目的升序就没有任何使用了,就很吃亏,所以现在进入算法原理。

算法原理:

使用双指针算法,对于题目中的升序,一定要利用好,我们知道:

target = num1 + num2

那么既然是升序的,如果我们让两个指针,一个从开始走,一个从末尾走,也就是最大的和最小的走,判断结果,大于了target,右指针往左边走,反之亦然,这时候其实已经做完题目了。

对于循环来说,只有一个循环,如果没有找到,返回的是个空就可以。

算法编写:

class Solution 
{
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        int right = price.size() - 1, left = 0;
        while(left < right)
        {
            if(price[left] + price[right] == target)
                return {price[left],price[right]};
            else if(price[left] + price[right] < target) left++;
            else if(price[left] + price[right] > target) right--;
        }
        return { };
    }
};

结束条件自然是左小于右,因为返回的是vector,都没有找到的话返回空即可,时间复杂度是O(N),没有新开空间,所以空间复杂度为O(1)。


三数之和

题目解析

由题目可得,找三个数,其中这三个数相加等于0,我们不妨将题目理解为,找一个数,该数 = 另外两数之和,是不是就感觉容易多了?不过是上文和为s的变种而已,我们只是需要将S变化一下即可。

以上是题目的最基本的要求,那么还有一个要求是,不允许出现重复的,这是和本文第一道题不同的要求,这点代表了我们要去重即可。

那么同样的,我们思考如何暴力解法?

暴力解法无非是将所有的三元组列出来,判断和是否为零,满足条件,我们可以将它丢进set,用set本身的性质进行去重即可。

但是暴力解法的时间复杂度可就高了,三个数都要单独列出,也就是需要三个循环,时间复杂度为O(N^3),往往是通过不了的。

所以,我们进入到算法原理方面。


算法原理

我们同样的使用双指针算法,因为是双指针不是三指针,所以需要我们固定一个数,用来充当target,有了第一个题目的经验,我们不妨排序一下,保证数组有序的同时有利于我们控制指针变量,排序之后对于我们去重的操作也会容易很多。

排序之后,固定好target,然后进入到第二个循环,通过双指针算法,找两个数,使该三个数相加等于0即可。

那么指针移动分为两种情况,如果前面两个数相加>target,代表right大了,需要right--,反之亦然,这是移动的情况。满足条件的话,添加进去就可以了。

那么最重要的点来了,我们如何进行去重操作呢?

判断的是nums[left] == nums[left + 1]是否相等即可,如果相等了,left就++,right同理,但是去重的不只有这两个数,还有一个数也需要去重,就是nums[i],如果i不去重,肯定是很导致很多重复的元素,毕竟都是会从头开始找的。

去重i的时候,需要控制i的移动,因为去重操作本身就会控制指针移动。


算法编写

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

三个去重,一个排序,三个判断,最后返回即可。


感谢阅读!