首页 > 编程语言 >双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动(3)

双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动(3)

时间:2024-11-07 17:44:18浏览次数:3  
标签:一慢 须臾之间 right target nums int 一快 vector left

前言:本篇来到双指针算法介绍的最终篇,该文将通过三个同类型但难度逐渐累增的题目,再次强化对双指针算法的理解和运用。

 相关题目及讲解

一. 两数之和

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

题目分析:

1. 该题要求较为简单,只需要在数组中查找两个和为target的元素,并将他们储存在需要返回的数组中即可。

2. 需要注意找到任一一对即可返回,无需返回多种情况。

思路讲解:

解法一:暴力解法(会超时)

很容易想到采用两个for循环直接逐个遍历的方式,符合要求即可直接返回。 

代码示例如下:

class Solution {
public:
 vector<int> twoSum(vector<int>& nums, int target) {
 int n = nums.size();
 for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数
 for (int j = i + 1; j < n; j++) { // 第⼆层循环从 i 位置之后列举第⼆个数
 if (nums[i] + nums[j] == target) // 两个数的和等于⽬标值,说明我们已经找到结果了
 return {nums[i], nums[j]};
 }
 }
 return {-1, -1};
 }
};

 解法二:对撞指针

基于解法一遍历思想的基础之上,我们对其通过减少遍历次数进行优化。

1. 首先对数组进行排序

2. 定义left=0,right=n-1,分别位于数组的左右两侧,代表最小和最大值。

3. 用sum表示nums[left]与nums[right]的和,与target比较。

如果sum>target,则此时和过大,应该让right--

如果sum<target,则此时和过小,应该让left++

如果sum=target,插入返回的数组中直接返回即可

代码实现:

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

二. 三数之和

题目链接:15. 三数之和 - 力扣(LeetCode) 

题目分析:

1. 需要在一个数组内查找三个相加后和为0的元素

2. 这三个元素不能重复,但元素的值可以相同

3. 输出中不能包含内容相同的三元数组

思路讲解:

解法一: 暴力解法(会超时) 

思路与两数之和大致相同,只是需要再嵌套一层for循环代表第三个数即可。

此时时间复杂度已经来到了恐怖的O(n^3),基本上是一定会超时的。

解法二:对撞指针 

1. 首先排序数组

2. 在求解两数之和时,我们就采取了对撞指针的方法,那么此时是三数之和,我们只需要固定一个数,在该数右侧的区间内使用对撞指针即可。

3. 使用for循环初始化一个i,那么i表示的就是我们需要固定的值,令left=i+1,right=n-1,重复两数之和的操作即可。只不过这次所求的target为-nums[i]。

4. 在查找到符合条件的元素时,我们将nums[i],nums[left],nums[right]插入要返回的数组中,并进行去重操作:

由于每一轮插入成功后,都会令left++,right--,此时要考虑以下几种情况进行去重:

1) 当nums[left]=nums[left-1]时,说明此处的left元素与上一个插入的相同,因此需要left++进行跳过。

2) 当nums[right]=nums[right+1]时,说明此处的right元素与上一个插入的相同,因此需要right--进行跳过。

注意:循环和去重操作均需满足条件left<right!!!

5. i的去重操作与上基本相同。

代码实现:

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;)
        {
            int target=-nums[i];
            if(target<0)
            {
                break;
            }//说明元素全部大于0,不存在满足的情况
            int left=i+1,right=n-1;
            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]});
                    left++;
                    right--;
                     while(left<right&&nums[left]==nums[left-1])
                {
                    left++;
                }
                while(left<right&&nums[right]==nums[right+1])
                {
                    right--;
                }
                }
               
            }
            i++;
            while(i<n&&nums[i]==nums[i-1])
            {
                i++;
            }

        }
        return ret;
        
    }
};

三. 四数之和

题目链接:18. 四数之和 - 力扣(LeetCode)

题目分析:

1. 从数组内寻找4个加起来和为target的元素插入到需要返回的数组中

2. 元素不可以重复

3. 元素所代表的值可以重复

4. 需要返回所有情况

思路讲解:

1. 首先排序数组

2. 基于三数之和的思想,我们只需要固定一个数,在其右侧的区间进行三数之和的对撞指针和去重操作即可。

3. 需注意固定的这个数字在遍历的时候也需要去重。

代码实现:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());//排序
        vector<vector<int>> ret;
        int n=nums.size();
        for(int i=0;i<n;)
        {
            for(int j=i+1;j<n;)
            {
                int left=j+1,right=n-1;
                long long flag=(long long)target-nums[i]-nums[j];
                while(left<right)
                {
                    int sum=nums[left]+nums[right];
                    if(sum<flag)
                    {
                        left++;
                    }
                    else if(sum>flag)
                    {
                        right--;
                    }
                    else
                    {
                        ret.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<n&&nums[j]==nums[j-1])
                    {
                        j++;
                    }
                
            }
            i++;
                while(i<n&&nums[i]==nums[i-1])
                {
                    i++;
                }
        }
        return ret;
        
    }
};

 小结:

对双指针算法的讲解就先告一段落啦,敬请期待下篇关于滑动窗口算法的介绍,欢迎各位佬前来支持斧正!!!

 

 

 

 

 

 

标签:一慢,须臾之间,right,target,nums,int,一快,vector,left
From: https://blog.csdn.net/2303_81060385/article/details/143601155

相关文章

  • 初学者友好!从零到一快速上手PyCharm安装的超详细图解+避坑指南教程
    一,pycharm的官网下载下载地址:www.jetbrains.com/pycharm/本文将从Python解释器安装到Pycharm专业版安装和配置汉化等使用都进行了详细介绍,希望能够帮助到大家。Python解释器&Pycharm安装包&Pycharm破姐插件我都打包好了。 ......
  • 鲜花:六一快乐
    我睁开眼,发现自己正躺在一片巨大的草地上,而我头顶上则是一片彩虹色的天空,渐变的各种色彩杂糅在一起,而四周则是齐腰深的绿草。我撑住地面站起身,一阵风刮来,带着放线菌的气味,草儿们也被吹着弯下了腰,一只粉色兔子突然从乱草中窜了出来,翻了个身又钻回了草中,接下来只能看见草儿们被兔子......
  • 五•一颂|广州流辰信息致敬每一个辛勤的劳动者,祝大家五一快乐!
    时光飞逝,一年一度的五一国际劳动节如期而至。在这个竞争激烈的社会中,拥有勤劳品质的人儿总会在适当的时机迎来人生的高光时刻。或许你的人生经历非常丰富,或顺利,或坎坷,不管是哪种状态,勤劳的人应该是这个时代值得尊敬的人。正值五一国际劳动节来临之际,广州流辰信息感恩这个伟大的时......
  • 算法学习笔记五一快速排序
    目录什么是快速排序算法思想示例代码什么是快速排序快速排序(Quicksort)是一种常用的排序算法,它的基本思想是通过分治的策略将一个大问题划分为多个小问题来解决。它的平均时间复杂度为O(nlogn),最坏情况(有序情况)为O(n^2)。是一种高效的排序算法。算法思想选择一个基准元素(pivot......
  • 双十一快递业务量暴增,快递驿站视频智能监控方案保障快递业务顺利开展
    一、背景分析虽然刚刚过去的双十一电商购物狂潮结束,但是快递业务量仍处在高峰期。据数据统计,今年全国邮政快递企业在11月11日当天共揽收快递包裹6.39亿件,是平日业务量的1.87倍,同比增长15.76%。随着电商购物节的不断增多,快递行业的业务量也逐渐上涨,为保障快递配送业务的正常进行、让......
  • 双十一快递业务量暴增,快递驿站视频智能监控方案保障快递业务顺利开展
    一、背景分析虽然刚刚过去的双十一电商购物狂潮结束,但是快递业务量仍处在高峰期。据数据统计,今年全国邮政快递企业在11月11日当天共揽收快递包裹6.39亿件,是平日业务量的1.87倍,同比增长15.76%。随着电商购物节的不断增多,快递行业的业务量也逐渐上涨,为保障快递配送业务的正常进行、......
  • 大一快结束了,一年都没跟上进度怎么办
     本人是某沿海四非的计算机专业学生,读大学以来,完全没有跟上一节课,感觉效率极低,不过笔者喜欢打乒乓球,乒乓球界有一句话叫球不落地,永不放弃。所以接下来我要开学啦,把我的天赋拿回来,嘻嘻嘻,颇为自恋。......