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

15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

提示:

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/3sum

题解

思路

  1. 开头容易让人想到三层循环+hash去重,但时间复杂度和空间消耗比较大

  2. 使用排序+双指针;达到去除重复值的作用

  3. 还要明确几个条件:

    • 数组为空或数组长度小于三
    • 排序后,最小值为正数,就不可能存在想加为0 的情况
    • 有连续重复的数字,要往后移,这样就能保证去重的效果
    • 若三个数组位的值想加等于0;还要考虑他们之后的情况,是否又有重复的值
    • 若三个数组位的值相加小于零,要考虑将L向后移一位
    • 若三个数组位的值相加大于零,要考虑将R向前移一位
class Solution {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans=new ArrayList();int len=nums.length;if(nums==null||len<3){return ans;//如果数组的长度小于3 或者数组为空,返回值为空}//对数组排序Arrays.sort(nums);//时间复杂度为nlognfor(int i=0;i<len;i++){if(nums[i]>0){break;}//最小的都大于0,不可能存在加起来等于0的情况if(i>0&&nums[i]==nums[i-1]) continue;//相邻值相同,去重int L=i+1;int R=len-1;while(L<R){int sum=0;sum=nums[i]+nums[R]+nums[L];if(sum==0){ans.add(Arrays.asList(nums[i],nums[L],nums[R]));while(L<R&&nums[L]==nums[L+1]) L++;while(L<R&&nums[R]==nums[R-1]) R--;L++;R--;}else if(sum<0) L++;else if(sum>0) R--;}}return ans;}
}

相关文章:

15. 三数之和

给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的三元组。 示例 …...

40-Golang中的文件

Golang中的文件基本介绍文件的打开和关闭读文件操作应用实例写文件操作实例判断文件是否存在基本介绍 文件在程序中是以流的形式存在的 流&#xff1a;数据在数据源(文件)和程序(内存)之间经历的路程 输入流&#xff1a;数据从数据源到程序之间的路径 输出流&#xff1a;数据…...

Springboot整合RabbitMQ并使用

1、Springboot整合RabbitMQ 1、引入场景启动器 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </dependency>引入AMQP场景启动器之后&#xff0c;RabbitAutoConfiguratio…...

Java中方法引用(引用静态方法、引用成员方法(引用其他类的成员方法、引用本类的成员方法、引用父类的成员方法)、引用构造方法、其他调用方式、小练习)

方法引用&#xff1a;把已经存在的方法拿过来用&#xff0c;当作函数式接口中抽象方法的方法体 我们前面学到Arrays工具类中的sort方法&#xff0c;当我们需要指定排序规则时&#xff0c;需要传递Comparator接口的实现类对象&#xff0c;我们之前使用匿名内部类类的形式作为参…...

整理了100道关于Python基础知识的练习题,记得收藏~

实例1.数字组合 题目&#xff1a; 有四个数字&#xff1a;1、2、3、4&#xff0c;能组成多少个互不相同且无重复数字的三位数&#xff1f;各是多少&#xff1f; 程序分析&#xff1a; 遍历全部可能&#xff0c;把有重复的剃掉。 total0 for i in range(1,5):for j in range(…...

OSG三维渲染引擎编程学习之七十七:“第七章:OSG场景图形交互” 之 “7.8 场景交互”

目录 第七章 OSG场景图形交互 7.8 场景交互 7.8.1 osgGA库 7.8.2 事件消息处理 7.8.3 程序抓图示例...

797.差分

输入一个长度为 n的整数序列。 接下来输入 m个操作&#xff0c;每个操作包含三个整数 l,r,c&#xff0c;表示将序列中 [l,r] 之间的每个数加上 c。 请你输出进行完所有操作后的序列。 输入格式 第一行包含两个整数 n和 m。 第二行包含 n个整数&#xff0c;表示整数序列。 …...

为什么说要慎用BeanUtils,因为性能真的拉跨

1 背景之前在专栏中讲过“不推荐使用属性拷贝工具”&#xff0c;推荐直接定义转换类和方法使用 IDEA 插件自动填充 get / set 函数。不推荐的主要理由是&#xff1a;有些属性拷贝工具性能有点差有些属性拷贝工具有“BUG”使用属性拷贝工具容易存在一些隐患&#xff08;后面例子…...

【项目设计】高并发内存池(六)[细节优化+测试]

&#x1f387;C学习历程&#xff1a;入门 博客主页&#xff1a;一起去看日落吗持续分享博主的C学习历程博主的能力有限&#xff0c;出现错误希望大家不吝赐教分享给大家一句我很喜欢的话&#xff1a; 也许你现在做的事情&#xff0c;暂时看不到成果&#xff0c;但不要忘记&…...

同模块设置不同应用主题方案

有时候公司内部会有不同应用但是有部分模块功能一样&#xff0c;只根据应用角色有些细节逻辑区分的场景。这时候往往采用模块化采用以应用至不同的APP。如果APP主题不一致&#xff0c;该如果解决。 方案&#xff1a; 在不同应用的config.gradle 下面根据不同应用定义不同的a…...

centos7 安装 hyperf

​​​​​​PHP > 7.4 Swoole PHP 扩展 > 4.5&#xff0c;并关闭了 Short Name OpenSSL PHP 扩展 JSON PHP 扩展 PDO PHP 扩展 Redis PHP 扩展 Protobuf PHP 扩展 composer create-project hyperf/hyperf-skeleton 推荐安装项 全部选n php.ini [swoole] extens…...

RZ/G2UL核心板-40℃低温启动测试

1. 测试对象HD-G2UL-EVM基于HD-G2UL-CORE工业级核心板设计&#xff0c;一路千兆网口、一路CAN-bus、 3路TTL UART、LCD、WiFi、CSI 摄像头接口等&#xff0c;接口丰富&#xff0c;适用于工业现场应用需求&#xff0c;亦方便用户评估核心板及CPU的性能。HD-G2UL-CORE系列工业级核…...

PyQt5可视化 7 饼图和柱状图实操案例 ①Qt项目的创建

目录 一、新建Qt项目 二、添加组件和布局 三、添加资源 1. 新建资源文件 2. 添加图标资源 四、frameHead 1. toolBtnGenData 2. toolBtnCounting 3. comboTheme 4. comboAnimation 5. Horizontal Spacer 6. toolBtnQuit 7. 设置toolBtnQuit的功能 8. frameHead的…...

0104路径搜索和单点路径-无向图-数据结构和算法(Java)

文章目录2 单点路径2.1 API2.2 算法实现后记2 单点路径 单点路径。给定一幅图和一个起点s&#xff0c;回答“从s到给定的目的顶点v是否存在一条路径&#xff1f;如果有&#xff0c;找出这条路径。”等类似问题。 2.1 API 单点路径问题在图的处理邻域中十分重要。根据标准设计…...

Maxscale读写分离实施文档

Maxscale介绍 MaxScale是maridb开发的一个mysql数据中间件&#xff0c;其配置简单&#xff0c;能够实现读写分离&#xff0c;并且可以根据主从状态实现写库的自动切换。 使用Maxscale无需对业务代码进行修改&#xff0c;其自带的读写分离模块&#xff0c;能够解析SQL语句&…...

websocket实现一个简单聊天框

websoket在客户端的使用 事件&#xff1a;open/message/error/close 方法&#xff1a;send/close var socket new WebSocket(url)// 服务连接成功时触发 socket.addEventListener(open, function() {console.log("连接成功了") })// 主动给websocket发消息 socket…...

Docker-安装应用

一、安装Tomcat 注意:新版Tomcat安装之后启动访问会出现404 修改:删除原有的webapps目录,修改webapps.dist为webapps 免修改版本:billygoo/tomcat8-jdk8 二、安装Mysql 1、安装 拉取镜像 docker pull mysql:5.7 运行镜像…...

Web3中的营销:如何在2023年获得优势

Mar. 2022, Daniel在过去的一年里&#xff0c;让人们对你的Web3项目或协议感兴趣已经变得越来越有挑战性。许多曾经充满希望的项目因为各种不同的原因&#xff0c;都在熊市中倒下了。然而&#xff0c;那些迄今为止幸存下来的项目都有一个共同点&#xff1a;强大的社区。Web3营销…...

Java中==和equals区别

文章目录Java中和equals区别1. Integer中和equals的问题1.1 Integer类型且不是通过new创建的比较1.2 手动new Integer()创建的比较1.3 Integer和int比较2. String中和equals的问题3. DemoJava中和equals区别 equals是方法&#xff0c;是运算符&#xff1a; 如果比较的对象是基…...

计算机科学导论笔记(三)

五、计算机组成 计算机组成部件可以分为三大类&#xff08;子系统&#xff09;&#xff1a;中央处理单元&#xff08;CPU&#xff09;、主存储器和输入/输出子系统。 5.1 中央处理单元&#xff08;CPU&#xff09; 中央处理单元用于数据的运算&#xff0c;分为算术逻辑单元&a…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...