当前位置: 首页 > article >正文

【优先算法】双指针 --(结合例题讲解解题思路)(C++)

目录

​编辑

1. 题目:三数之和

1.1算法思路 

1.2代码实现

 2.题目:四数之和

2.1算法思路

2.2代码实现


 

1. 题目:三数之和

力扣-三数之和icon-default.png?t=O83Ahttps://leetcode.cn/problems/3sum/

 

1.1算法思路 

方法一:暴力解法 

三层for循环,一个一个去找。因为有重复的,所以我们要将数据放进set,去重。

总结,这种方法,时间复杂度太高,如果用这个方法,难度根本没有,所以面试官想要的根本不是这种!!!

方法二:双指针

第一步,排好序 

第二步,固定一个数 a,因为题干说,三个数和==0,那么,我只需要在固定的这个数,的后面的区间利用“双指针”找到两个数,和== -a 即可。

 

当然,在过程中,我们需要特别注意的是,做到不重,不漏。

第三步,不漏

就是在left,right在移动过程中,找到了符合条件的之后,还要继续在区间查找。

第四步,不重

做到去重,就是每次找到符合条件的数,left++,right--,但是如果变化之后的数还是与之前的一样nums[left]==nums[left-1] 或者 nums[right]==nums[right+1]  此时,我们需要继续++或--

!!!但是注意,不要越界需要有限制条件left < right。

1.2代码实现

暴力解法的代码实现,我这就不写了。双指针的解法思路也是有两种,例如下 方法一和方法二

 

 

 2.题目:四数之和

力扣-四数之和icon-default.png?t=O83Ahttps://leetcode.cn/problems/4sum/description/

 

2.1算法思路

四数之和算法思路和三数之和是一样的,唯一的差别就是,四数定了两个固定数(并不是完全固定的数哈!!!咱们脑子要灵活一点)

第一步,定第一个数 a=nums[i]

第二步,定第二个数 b=nums[x]

第三步,定left,right。(注意,{ a,b,nums[left],nums[right] }就是我们符合要求的数)

其余步骤也就和三数之和一样,做到,不重,不漏。唯一差别就是这里多了一步,b的去重。

 

2.2代码实现

本期学习到此结束,感谢大家支持!!! 

原文地址:https://blog.csdn.net/2301_80362419/article/details/144629931
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/446287.html

相关文章:

  • 嵌入式入门Day38
  • maven高级(day15)
  • STM32的存储结构
  • 数据挖掘实训:天气数据分析与机器学习模型构建
  • css出现边框
  • 单元测试MockitoExtension和SpringExtension
  • 【java】全文索引,普通索引,以及ES搜索引擎组件的关系
  • MATLAB中cvx工具箱的使用
  • 三次翻转实现数组元素的旋转
  • 深入了解Python模拟负载均衡器:将请求高效分发至多个服务器
  • Emacs折腾日记(四)——elisp控制结构
  • Django 模板分割及多语言支持案例【需求文档】-->【实现方案】
  • springboot 3 websocket react 系统提示,选手实时数据更新监控
  • Flask内存马学习
  • (12)YOLOv10算法基本原理
  • 基于语义的NLP任务去重:大语言模型应用与实践
  • 数据结构-栈与队列
  • GaussDB数据库迁移方案介绍
  • 某医疗行业用户基于Apache SeaTunnel从调研选型到企业数据集成框架的落地实践
  • 智慧商城:购物车模块基本静态结构 + 构建vuex cart模块,获取数据存储(异步actions)
  • 图解HTTP-HTTP状态码
  • ECharts散点图-SymbolShapeMorph,附视频讲解与代码下载
  • Go 语言GC(垃圾回收)的工作原理
  • 「Mac畅玩鸿蒙与硬件45」UI互动应用篇22 - 评分统计工具
  • 前端笔记——大数据量浏览器卡顿优化思路
  • 青少年编程与数学 02-004 Go语言Web编程 06课题、RESTful API