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

剑指offer 7 数组中和为0的三个数

此问题属于nsum问题,题目链接:力扣

要求在数组中找到不重复的三元组,三个数加起来为0,且每个下标只能用一次。而且需要返回所有这样的不重复数组。

1. 排序 + 双指针

1. 「不重复」的本质是什么?我们保持三重循环的大框架不变,只需要保证:

  • 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素;
  • 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说,我们枚举的三元组 (a, b, c) 满足 a ≤ b ≤ c,保证了只有 (a, b, c) 这个顺序会被枚举到,而(b, a, c)、(c, b, a) 等等这些不会,这样就减少了重复。要实现这一点,我们可以将数组中的元素从小到大进行排序,随后使用普通的三重循环就可以满足上面的要求。

2. 对于每一重循环而言,相邻两次枚举的元素不能相同,否则也会造成重复,(但是对于初学者来讲,为了简化题目,可以先不考虑重复结果的处理)

2. 不考虑重复

我们可以先考虑不处理重复结果的情况,代码如下:(注释全整版)

    public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums); // 排序是前提List<List<Integer>> ans = new ArrayList<>();// 枚举 afor (int a = 0; a < n; a++) {int c = n - 1; // 将c初始指向数组最后一位int target = -nums[a]; // 这是b和c的目标和for (int b = a + 1; b < n; b++) { // b 暂时固定(按部就班的递增)while (b < c && nums[b] + nums[c] > target){c--;}// 如果b和c的和太大,c就左移if (c == b) break; // a b 确定下,c已经退无可退了,所以break// 后续就算是b再递增,这个总和也是太大,没有合适的c了if (nums[b] + nums[c] == target){List<Integer> list = new ArrayList<>();list.add(nums[a]);list.add(nums[b]);list.add(nums[c]);ans.add(list);}}}return ans;}

其实不加处理重复的话,代码很简单哈哈!!!

3.加上对重复的判定

后续对于重复答案的处理,就是要求a不重复,b不重复,在代码中分别加上这两段验证即可:

1. 对于a: 

if (a > 0 && nums[a] == nums[a - 1]) continue;

2. 对于b

if (b > a + 1 &&  nums[b] == nums[b - 1]) continue;

由以上思路得出的本题目的完整版代码如下:(注释完整版)

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for (int a = 0; a < n; a++) {if (a > 0 && nums[a] == nums[a - 1]) continue; // 每个数只能当一次aint c = n - 1;int target = -nums[a];// 枚举bfor (int b = a + 1; b < n; b++) { // b从a后一个开始if (b > a + 1 && nums[b] == nums[b - 1]) continue; // b > a+1代表// 比如说 0 1 1这个数组,如果a指向0,b指向第二个1,那就没必要了// 因为每个数字只能当一次bwhile (b < c && nums[b] + nums[c] > target) {--c;}// 如果指针重合,随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环if (b == c) {break;}if (nums[b] + nums[c] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[a]);list.add(nums[b]);list.add(nums[c]);res.add(list);}}}return res;}
}

时间复杂度O(n^{^{2}}),在n <= 3000的数据范围内可以满足要求

相关文章:

剑指offer 7 数组中和为0的三个数

此问题属于nsum问题&#xff0c;题目链接&#xff1a;力扣 要求在数组中找到不重复的三元组&#xff0c;三个数加起来为0&#xff0c;且每个下标只能用一次。而且需要返回所有这样的不重复数组。 1. 排序 双指针 1. 「不重复」的本质是什么&#xff1f;我们保持三重循环的大…...

DockerFile

大家想想&#xff0c;Nginx&#xff0c;tomcat&#xff0c;mysql 这些镜像都是哪里来的&#xff1f;官方能写&#xff0c;我们不能写吗&#xff1f; 我们要研究自己如何做一个镜像&#xff0c;而且我们写的微服务项目以及springboot打包上云部署&#xff0c;Docker就是最方便的…...

Vue-Router 介绍及路由原理分析

文章目录Vue-Router 路由模式单页面与传统页面跳转的区别Hash 模式History 模式abstract 模式原理解析Hash 模式原理History 模式原理路由使用引入 Vue-Router获取全局路由跳转参数的变化获取路由中带的参数重定向页面Vue-Router 路由模式 单页面与传统页面跳转的区别 单页面…...

git代码提交后jenkins构建和自动部署

利用jenkins和gitlab的webhook结合&#xff0c;实现提交代码之后&#xff0c;自动触发jenkins的构建。顺带介绍一下通过触发器构建&#xff0c;比如直接通过url去触发的方式。 一、jenkins结合webhook 1、jenkins配置 a、首先jenkins得需要安装两个gitlab的插件&#xff1a;(…...

2023面试题目总结

项目遇到的问题难点&#xff1f; 老项目版本过低(angular4),相关框架太少&#xff0c;需要升级成新框架。 1.single-spa 2.qiankun 3.iframe 样式环境隔离/js隔离/公共依赖的加载 JS 原型&#xff0c;原型链&#xff0c;new 原型是存放公共属性地方&#xff0c;所有实例都…...

Vue常用指令及声明周期

文章目录知识点前端开发环境配置v-text && v-htmlv-if、v-else && v-showv-forv-onv-modelv-bind、v-cloak、v-pre&&v-once全局 API 是什么Vue.directive 自定义组件Vue.directive 是什么自定义组件回调函数参数自定义组件的生命周期Vue.set 全局操作为…...

MariaDB 成功敲钟上市 | 它与 Navciat 缘起 10 年前

MariaDB 敲钟上市2022 年底&#xff0c;云数据库公司 MariaDB 与 Angel Pond Holdings 公司完成合并&#xff0c;并在纽交所上市。新公司更名为 MariaDB&#xff0c;MySQL 之父奋斗了13年终敲钟。这标志着 MariaDB 开启新篇章。无论从开源还是商业之路&#xff0c;都将成为业内…...

LESS模型与随机森林

模型学习 1 随机森林 https://blog.csdn.net/weixin_35770067/article/details/107346591? 森林就是建立了很多决策树&#xff0c;把很多决策树组合到一起就是森林。 这些决策树都是为了解决同一任务建立的&#xff0c;最终的目标也都是一致的&#xff0c;最后将其结果来平均…...

如何利用Power Virtual Agents机器人实现成绩查询服务

今天我们继续介绍如何利用Power Virtual Agents来实现成绩查询服务。设计思路是在PVA聊天机器人的对话框中输入学生的姓名和学号来进行成绩的查询。首先&#xff0c;在Microsoft 365的OneDrive中制作一个Excel格式的成绩单。 可以将学生的学号、姓名、各学科成绩进行添加。 在P…...

flavor 配置

文章目录1. flavorDimensions1.1 单维度1.2 多维度2. BuildConfig3. sourceSets4. 参考资料1. flavorDimensions 与 productFlavors 配合使用使用 flavorDimensions 定义风味维度&#xff0c;维度越多&#xff0c;能打出的渠道包越丰富 1.1 单维度 defaultConfig {...flavor…...

《第一行代码》 第五章:详解广播机制

如果你了解网络通信原理应该会知道&#xff0c;在一个 IP 网络范围中最大的IP 地址是被保留作为广播地址来使用的。比如某个网络的 IP 范围是 192.168.0XXX&#xff0c;子网掩码是255.255.255.0那么这个网络的广播地址就是 192.168.0255广播数据包会被发送到同-网络上的所有端口…...

Leetcode(每日一题)——1139. 最大的以 1 为边界的正方形

摘要 1139. 最大的以 1 为边界的正方形 一、以1为边界的最大正方形 1.1 动态规划 第530题需要正方形所有网格中的数字都是1&#xff0c;只要搞懂动态规划的原理&#xff0c;代码就非常简洁。而这题只要正方形4条边的网格都是1即可&#xff0c;中间是什么数字不用管。 这题…...

YOLOv5:GitHub两万八Star项目

来源&#xff1a;投稿 作者&#xff1a;王同学 编辑&#xff1a;学姐 Yolov5详解 官方源码仓库&#xff1a;https://github.com/ultralytics/yolov5 相关论文&#xff1a;未发表&#xff08;改进点都被你们抢先发了&#xff09; 0 前言 截止到2022年7月&#xff0c;Yolov5项…...

袋鼠云产品功能更新报告04期丨2023年首次,产品升级“狂飙”

新的一年我们加紧了更新迭代的速度&#xff0c;增加了数据湖平台EasyLake和大数据基础平台EasyMR&#xff0c;超40项功能升级优化。我们将继续保持产品升级节奏&#xff0c;满足不同行业用户的更多需求&#xff0c;为用户带来极致的产品使用体验。 以下为袋鼠云产品功能更新报…...

如何在Power Virtual Agents中使用Power Automate

今天我们来介绍一下如何在Power Virtual Agents中使用PowerAutomate。我们以通过在PVA聊天机器人的对话框中输入“发布通知”后会把预设好的通知信息自动发布到Teams中的某个团队中为例。首先进入PVA聊天机器人编辑界面后选择“主题”-“新建主题”。 在“新建主题”中添加“触…...

BXC6332A第二代智能头盔方案助力电动车市场,为安全保驾护航

随着2020年6月1日起&#xff0c;公安部交管局在全国开展“一盔一带”安全守护行动&#xff0c;摩托车、电动车驾驶人乘车人按照规定正确使用头盔&#xff0c;是保障司乘安全的一道重要屏障&#xff0c;据统计&#xff0c;摩托车、电动自行车驾乘人员死亡事故中约80%为颅脑损伤致…...

浮点数值计算精度丢失问题剖析及解决方法

文章目录1、原因分析2、解决方法2.1、Java中使用 BigDecimal 类2.2、JavaScript 中解决计算精度丢失的问题3、使用建议1、原因分析 首先我们来看个反直觉的浮点数值计算 System.out.println(0.3*3);有的同学可能要问为啥不是0.9&#xff1f; 首先要知道为什么会产生这个问题…...

字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)

朴素的字符串匹配算法又称为暴力匹配算法&#xff08;Brute Force Algorithm&#xff09;&#xff0c;最为简单的字符串匹配算法。算法简介朴素的字符串匹配算法又称为暴力匹配算法&#xff08;Brute Force Algorithm&#xff09;&#xff0c;它的主要特点是&#xff1a;没有预…...

CVE-2021-42278 CVE-2021-42287域内提权漏洞

漏洞介绍2021 年 11 月 9 日&#xff0c;国外研究员在推特上发布了AD相关的 CVE&#xff0c;CVE-2021-42278 & CVE-2021-42287 &#xff0c;两个漏洞组合可导致域内普通用户权限提升至域管权限。CVE-2021-42278&#xff1a;是一个安全绕过漏洞&#xff0c;允许通过修改机器…...

关于IcmpSendEcho2的使用和回调问题

由于我的需求是短时间内ping多台机子&#xff0c;所以需要异步执行&#xff0c;微软提供的例子是同步方式的&#xff0c;根据微软官方提供的icmpSendEcho2 函数的信息 &#xff0c;我需要定义一个空的宏PIO_APC_ROUTINE_DEFINED &#xff0c;定义完之后&#xff0c;编译又出现…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

从零开始了解数据采集(二十八)——制造业数字孪生

近年来&#xff0c;我国的工业领域正经历一场前所未有的数字化变革&#xff0c;从“双碳目标”到工业互联网平台的推广&#xff0c;国家政策和市场需求共同推动了制造业的升级。在这场变革中&#xff0c;数字孪生技术成为备受关注的关键工具&#xff0c;它不仅让企业“看见”设…...