C++ 优先算法 —— 三数之和(双指针)

目录
题目:三数之和
1. 题目解析
2. 算法原理
①. 暴力枚举
②. 双指针算法
不漏的处理:
去重处理:
固定一个数 a 的优化:
3. 代码实现
Ⅰ. 暴力枚举(会超时 O(N³))
Ⅱ. 双指针算法 (O(N²))
题目:三数之和
1. 题目解析
题目截图:
题目中所述的顺序不重要有两种情况:
- 最终选出来的几个三元组里,每个三元组里的数据顺序,是可以不用考虑的。

- 最终选出来的几个三元组,三元组的顺序,也是可以不用考虑的。

题目中还要求元素不能相同:


题目的细节要求也就是:
- 最终选出来的几个三元组里面的元素是对应不同的
- 返回的三元组及其三元组里的数据的顺序不重要。
题目给的示例二就是没有最终结果的情况
2. 算法原理
这道题有两种解法:
- 暴力枚举(但会超时)
- 双指针算法
①. 暴力枚举
虽然暴力枚举会超时,这里还要介绍一下的,因为双指针解法就是基于暴力枚举进行优化的。
这里方法就是:排序+暴力枚举(从左往右)+去重
这里排序去重要注意的是:
所以可以换个策略,先对原数组整个排序:

所以,也就是先排序,再暴力枚举(从左往右枚举),再去重。
这样套三个for循环就可以暴力枚举结果了
//伪代码演示
for (int i = 0; i < n;) // 固定一个数a
{for (int j = i + 1; j < n;) //依次固定枚举第二个数{for (int k = j + 1; k < n;) //枚举第三个数{//查找符合的三元组,去重...}}}
(这里去重在下面双指针解法解释),这里套了三个for循环时间复杂度:O(N³)。
②. 双指针算法
这里双指针算法的解决方法就是:排序+双指针+去重
排序同上面暴力枚举,都先对一整个数组排序,再进行下面的处理。
这里举例一个已经排过序的新数组:
我们先固定一个数,这里先固定第一个数:

这里就转化成了和为s的两个数的问题,这里的s就是这个固定的数的相反数。也就是:

所以这里解决步骤:
- 先对整个数组排序
- 固定一个数 a(这里有个小优化,后续介绍)
- 在该数后面的区间内,利用双指针算法快速找到两个数的和为 -a 的即可。
注意:这里只是找到了符合条件的情况,并没有去重。
接下来就是处理细节问题了,也就是去重和确保所有符合条件的情况不落下(后面简称不漏) 。
和为s的两个数(这里会用到,详细介绍在此链接)
不漏的处理:
先控制指针找到符合情况:


这时可以看到是找到符合的情况了:
接下来就需要调整:

所以,也就是找到一种结果之后,不要停(两个指针不停),缩小区间(两指针都向内移动一步),继续寻找符合的情况。
去重处理:
去重要考虑两种情况:
- 找到一种结果之后,left和right指针要跳过重复的元素
(这里也就把第一个4给枚举完了)。
但这里固定的 a 还是为-4,再继续枚举,是肯定都是重复结果的。 - 所以当使用完一次双指针算法后,a也需要跳过重复的元素。

这里去重可能指针会越界,为了避免越界:
这里的越界问题不止对整个数组区间的越界,还有对要用双指针处理的区间可能会越界。
在实现去重代码时需要加个判断条件就可以解决:
要判断处理这个条件,既可避免越界
if(left < right)
也就判断两个指针是否在相遇前
固定一个数 a 的优化:

因为我们前面先排序该数组为升序了,所以固定数a就可以仅仅需要保证它≤0即可。
if (nums[i] > 0)
{break; // 小优化,数a为正数情况不用考虑,是一定不成立的
}
接下来实现代码。
3. 代码实现
题目链接:三数之和
Ⅰ. 暴力枚举(会超时 O(N³))
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1.排序sort(nums.begin(), nums.end());vector<vector<int>> ret; // 用来存储所有的三元组// 2.暴力枚举int n = nums.size();int i, j, k;for (i = 0; i < n;) // 固定一个数a{for (j = i + 1; j < n;) //依次固定枚举第二个数{for (k = j + 1; k < n;) //枚举第三个数{int sum = nums[i] + nums[j] + nums[k];if (sum == 0){ret.push_back({ nums[i],nums[j],nums[k] });}//去重++k;while (k < n && nums[k] == nums[k - 1]) {++k;}}//去重++j;while (j < n && nums[j] == nums[j - 1]) {++j;}}//去重++i;while (i < n && nums[i] == nums[i - 1]) {++i;}}return ret;}
};
提交记录:

测试用例:
Ⅱ. 双指针算法 (O(N²))
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 1.排序sort(nums.begin(), nums.end());vector<vector<int>> ret; // 用来存储所有的三元组// 2.利用双指针解决int n = nums.size();for (int i = 0; i < n;) // 固定一个数a{if (nums[i] > 0) {break; // 小优化,数a为正数情况不用考虑,是一定不成立的}// 定义left,right,target通过双指针获取相加等于0的组合int left = i + 1, right = n - 1, target = -nums[i];while (left < right) {int sum = nums[left] + nums[right];if (sum > target) {--right;} else if (sum < target) {++left;} else {// 将获取的三元组尾插ret里ret.push_back({nums[i], nums[left], nums[right]});// 将所有的情况获取--不漏,并去重// 缩小区间查找++left;--right;// 去重left和right,注意区间越界问题while (left < right && nums[left] == nums[left - 1]) {++left;}while (left < right && nums[right] == nums[right + 1]) {--right;}}}// 注意去重i++i;while (i < n && nums[i] == nums[i - 1]) {++i;}}return ret;}
};
注:这里时间复杂度是O(N²)。
提交记录:
制作不易,若有不足之处或出问题的地方,请各位大佬多多指教 ,感谢大家的阅读支持!!!
相关文章:
C++ 优先算法 —— 三数之和(双指针)
目录 题目:三数之和 1. 题目解析 2. 算法原理 ①. 暴力枚举 ②. 双指针算法 不漏的处理: 去重处理: 固定一个数 a 的优化: 3. 代码实现 Ⅰ. 暴力枚举(会超时 O(N)) Ⅱ.…...
YOLOv7-0.1部分代码阅读笔记-yolo.py
yolo.py models\yolo.py 目录 yolo.py 1.所需的库和模块 2.class Detect(nn.Module): 3.class IDetect(nn.Module): 4.class IAuxDetect(nn.Module): 5.class IBin(nn.Module): 6.class Model(nn.Module): 7.def parse_model(d, ch): 8.if __name__ __main__…...
【缓存与加速技术实践】Web缓存代理与CDN内容分发网络
文章目录 Web缓存代理Nginx配置缓存代理详细说明 CDN内容分发网络CDN的作用CDN的工作原理CDN内容的获取方式解决缓存集中过期的问题 Web缓存代理 作用: 缓存之前访问过的静态网页资源,以便在再次访问时能够直接从缓存代理服务器获取,减少源…...
MySQL的约束和三大范式
一.约束 什么是约束,为什么要用到约束? 约束就是用于创建表时,给对应的字段添加对应的约束 约束的作用就是当我们用insert into时,如果传入的数据有问题,不符合创建表时我们定的规定,这时MySQL就会自动帮…...
Unity网络通信(part7.分包和黏包)
目录 前言 概念 解决方案 具体代码 总结 分包黏包概念 分包 黏包 解决方案概述 前言 在探讨Unity网络通信的深入内容时,分包和黏包问题无疑是其中的关键环节。以下是对Unity网络通信中分包和黏包问题前言部分的详细解读。 概念 在网络通信中,…...
练习题 - DRF 3.x Overviewses 框架概述
Django REST Framework (DRF) 是一个强大的工具,用于构建 Web APIs。作为 Django 框架的扩展,DRF 提供了丰富的功能和简洁的 API,使得开发 RESTful Web 服务变得更加轻松。对于想要在 Django 环境中实现快速且灵活的 API 开发的开发者来说,DRF 是一个非常有吸引力的选择。学…...
Linux 经典面试八股文
快速鉴别十个题 1,你如何描述Linux文件系统的结构? 答案应包括对/, /etc, /var, /home, /bin, /lib, /usr, 和 /tmp等常见目录的功能和用途的描述。 2,在Linux中如何查看和终止正在运行的进程? 期望的答案应涵盖ps, top, htop, …...
Filter和Listener
一、Filter过滤器 1 概念 可以实现拦截功能,对于指定资源的限定进行拦截,替换,同时还可以提高程序的性能。在Web开发时,不同的Web资源中的过滤操作可以放在同一个Filter中完成,这样可以不用多次编写重复代码…...
Go 项目中实现类似 Java Shiro 的权限控制中间件?
序言: 要在 Go 项目中实现类似 Java Shiro 的权限控制中间件,我们可以分为几个步骤来实现用户的菜单访问权限和操作权限控制。以下是一个基本的实现框架步骤: 目录 一、数据库设计 二、中间件实现 三、使用中间件 四、用户权限管理 五…...
【Javascript】-一些原生的网页设计案例
JavaScript 网页设计案例 1. 动态时钟 功能描述:在网页上显示一个动态更新的时钟,包括小时、分钟和秒。实现思路: 使用 setInterval 函数每秒更新时间。获取当前时间并更新页面上的文本。 代码示例:<div id"clock"…...
SpringBoot开发——Spring Boot 3种定时任务方式
文章目录 一、什么是定时任务二、代码示例1、 @Scheduled 定时任务2、多线程定时任务3、基于接口(SchedulingConfigurer)实现动态更改定时任务3.1 数据库中存储cron信息3.2 pom.xml文件中增加mysql依赖3.3 application.yaml文件中增加mysql数据库配置:3.4 创建定时器3.5 启动…...
Flutter鸿蒙next 实现长按录音按钮及动画特效
在 Flutter 中实现长按录音按钮并且添加动画特效,是一个有趣且实用的功能。本文将通过实现一个具有动画效果的长按录音按钮,带领你一步步了解如何使用 Flutter 完成这个任务,并解释每一部分的实现。 一、功能需求 我们需要一个按钮…...
【计网】实现reactor反应堆模型 --- 框架搭建
没有一颗星, 会因为追求梦想而受伤, 当你真心渴望某样东西时, 整个宇宙都会来帮忙。 --- 保罗・戈埃罗 《牧羊少年奇幻之旅》--- 实现Reactor反应堆模型 1 前言2 框架搭建3 准备工作4 Reactor类的设计5 Connection连接接口6 回调方法 1 …...
力扣中等难度热题——长度为K的子数组的能量值
目录 题目链接:3255. 长度为 K 的子数组的能量值 II - 力扣(LeetCode) 题目描述 示例 提示: 解法一:通过连续上升的长度判断 Java写法: C写法: 相比与Java写法的差别 运行时间 时间复杂…...
JSON格式
JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,易于人和机器阅读和解析。它基于JavaScript的对象表示法,但被广泛用于多种编程语言。 JSON中的数据类型 字符串(String):用双引…...
O-RAN前传Spilt Option 7-2x
Spilt Option 7-2x 下行比特处理上行比特处理相关文章: Open Fronthaul wrt ORAN 联盟被称为下层拆分(LLS),其目标是提高电信市场的灵活性和竞争力。下层拆分是指无线电单元(RU) 和分布式单元(DU) 之间的拆分。 O-RAN前传接口可以在 eCPRI 上传输。eCPR…...
【GeoJSON在线编辑平台】(2)吸附+删除+挖孔+扩展
前言 在上一篇的基础上继续开发,补充上吸附功能、删除矢量、挖孔功能。 实现 1. 吸附 参考官方案例:Snap Interaction 2. 删除 通过 removeFeature 直接移除选中的要素。 3. 挖孔 首先是引入 Turf.js ,然后通过 mask 方法来实现挖孔的…...
确定图像的熵和各向异性 Halcon entropy_gray 解析
1、图像的熵 1.1 介绍 图像熵(image entropy)是图像“繁忙”程度的估计值,它表示为图像灰度级集合的比特平均数,单位比特/像素,也描述了图像信源的平均信息量。熵指的是体系的混乱程度,对于图像而言&#…...
大数据-214 数据挖掘 机器学习理论 - KMeans Python 实现 算法验证 sklearn n_clusters labels
点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…...
算法通关(3) -- kmp算法
KMP算法的原理 从题目引出 有两个字符串s1和s2,判断s1字符串是否包含s2字符串,如果包含返回s1包含s2的最左开头位置,不包含返回-1,如果是按照暴力的方法去匹配,以s1的每个字符作为开头,用s2的整体去匹配,…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
