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

LeetCode LCR 007. 三数之和 (Java)


题目描述

给定一个整数数组 nums,判断是否存在三个元素 a, b, c,使得 a + b + c = 0?找出所有满足条件且不重复的三元组。


解题思路

核心方法:排序 + 双指针

  1. 排序:首先将数组排序,便于后续去重和双指针操作。
  2. 固定第一个数:遍历数组,固定第一个数 a
  3. 双指针找剩余两数:对于固定的 a,使用左指针 left(初始指向 a 的下一个元素)和右指针 right(初始指向数组末尾),寻找满足 a + b + c = 0bc
  4. 去重:在遍历过程中,跳过重复元素以避免重复的三元组。

关键步骤详解

1. 排序的作用

排序后,相同的元素会相邻,便于后续跳过重复元素。例如,输入 [-1,0,1,2,-1,-4] 排序后为 [-4,-1,-1,0,1,2],相邻的 -1 可以方便地通过条件判断跳过。

2. 固定第一个数 a

遍历数组时,固定 a = nums[i]。若 a > 0,由于数组已排序,后面的数均为正数,无法满足三数之和为0,直接终止循环。

3. 双指针寻找 bc
  • 双指针初始化left = i + 1right = nums.length - 1
  • 调整指针
    • a + nums[left] + nums[right] < 0:需要增大总和,左指针右移。
    • a + nums[left] + nums[right] > 0:需要减小总和,右指针左移。
    • 若等于0:记录结果,并移动指针跳过重复元素。
4. 去重逻辑
  • a 去重:若当前 nums[i] 与前一个数相同(i > 0nums[i] == nums[i-1]),跳过以避免重复。
  • bc 去重:找到有效三元组后,跳过所有与当前 leftright 相同的元素。

代码实现

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> result = new ArrayList<>();int n = nums.length;for (int i = 0; i < n; i++) {if (nums[i] > 0) break; // 提前终止if (i > 0 && nums[i] == nums[i-1]) continue; // 对a去重int left = i + 1, right = n - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum < 0) left++;else if (sum > 0) right--;else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 对b和c去重while (left < right && nums[left] == nums[left+1]) left++;while (left < right && nums[right] == nums[right-1]) right--;left++;right--;}}}return result;
}

力扣通过截图

在这里插入图片描述


复杂度分析

  • 时间复杂度:O(n²)。排序 O(n log n),外层循环 O(n),内层双指针 O(n),总体 O(n²)。
  • 空间复杂度:O(1)。忽略结果存储空间,仅用常量空间。

示例解析

以输入 nums = [-1,0,1,2,-1,-4] 为例:

  1. 排序后数组[-4, -1, -1, 0, 1, 2]
  2. 固定 a = -4:双指针范围为 [-1, 2],无法找到和为4的组合。
  3. 固定 a = -1(第一个 -1):
    • left 指向第二个 -1right 指向 2,和为0,记录 [-1, -1, 2]
    • 调整指针跳过重复元素,继续找到 [-1, 0, 1]
  4. 后续元素去重:跳过重复的 a,最终得到结果。

总结

通过排序预处理,结合双指针高效寻找两数之和,同时在每一步跳过重复元素,确保结果唯一。这种方法巧妙地将时间复杂度降至 O(n²),是解决此类问题的经典思路。

相关文章:

LeetCode LCR 007. 三数之和 (Java)

题目描述 给定一个整数数组 nums&#xff0c;判断是否存在三个元素 a, b, c&#xff0c;使得 a b c 0&#xff1f;找出所有满足条件且不重复的三元组。 解题思路 核心方法&#xff1a;排序 双指针 排序&#xff1a;首先将数组排序&#xff0c;便于后续去重和双指针操作。…...

Spark的三种部署模式及其特点与区别

Spark支持多种集群部署模式&#xff0c;主要分为以下三类&#xff1a; 部署模式特点适用场景资源管理依赖Local模式单机运行&#xff0c;所有进程&#xff08;Driver、Executor&#xff09;在同一个JVM中开发调试、小规模数据测试无集群资源管理&#xff0c;仅本地线程模拟无需…...

2505d,d的借用检查器

void func(scope ref int*) {}unique(int*) a ...; assert(a !is null);unique(int*) b a; assert(a is null); assert(b !is null);func(b); // ok用live作为检查器,不必有断定了. int* a ...; int* b a; // 所有权转至b *a 3; // 不能再用a.编译器保证约束指针. live…...

前端EXCEL插件,智表ZCELL产品V3.0 版本发布,底层采用canvas全部重构,功能大幅扩展,性能极致提升,满足千万级单元格加载

本次更新是底层全部重构&#xff0c;按照现代浏览器要求&#xff0c;采用canvas方式进行了重构&#xff0c;预留了将来扩展空间&#xff0c;特别是在大数据量性能提升方面有了较大提升&#xff0c;可以满足千万级单元格加载&#xff0c;欢迎大家体验使用。 体验地址&#xff1…...

如何理解编程中的递归、迭代与回归?

作为编程初学者&#xff0c;递归、迭代和回归这三个概念常常让人感到困惑。本文将通过生活化的比喻、Python代码示例和直观的对比&#xff0c;帮助你彻底理解这三个重要概念及其应用场景。 一、从生活比喻理解核心概念 1. 递归&#xff08;Recursion&#xff09;—— 俄罗斯套…...

【金仓数据库征文】学校AI数字人:从Sql Server到KingbaseES的数据库转型之路

摘要&#xff1a;本文围绕学校 AI 数字人项目从 Sql Server 数据库替换至 KingbaseES 数据库的实践展开&#xff0c;涵盖迁移背景、两种数据库对比、替换实施步骤、应用效果展示、问题与解决措施等多方面内容&#xff0c;为教育领域类似项目提供了详实参考。 目录 1.背景与需求…...

stm32 lcd绘制波形和频谱

一、项目准备 主要利用LCD驱动中的画点和画连线函数&#xff0c;驱动是正点原子给我写好了的画点和画线的函数等些相关函数 void LCD_Draw_Circle(u16 x0,u16 y0,u8 r); //画圆 void LCD_DrawLine(u16 x1, u16 y1, u16 x2, u16 y2); //画线 二、画波形图函数实…...

深入理解卷积神经网络的输入层:数据的起点与预处理核心

内容摘要 本文围绕卷积神经网络输入层展开&#xff0c;详细介绍其在网络中的重要作用&#xff0c;包括接收不同领域数据的形式及传递数据的过程。深入解读数据预处理的关键操作&#xff0c;如去均值、归一化和PCA/白化。助力读者透彻理解输入层&#xff0c;为构建高效卷积神经…...

基于大模型与异步技术的股票分析系统实现

在金融量化分析领域&#xff0c;高效的数据获取与智能的策略决策是核心竞争力。本文结合异步数据抓取技术与大模型工具集成&#xff0c;构建一套完整的股票分析系统&#xff0c;实现从海量数据采集到智能信息查询的全流程自动化。 一、量化分析的数据基石&#xff1a;异步高效…...

BUCK基本原理学习总结-20250509

一、电感伏秒平衡特性 处于稳定状态的电感,开关导通时间(电流上升段)的伏秒数须与开关关断(电流下降段)时的伏秒数在数值上相等,尽管两者符号相反。这也表示,绘出电感电压对时间的曲线,导通时段曲线的面积必须等于关断时段曲线的面积。 二、BUCK的基本概念和原理 基…...

BERT类模型

1. BERT类模型是否需要处理 [CLS] 或池化&#xff1f; 那首先搞懂 [CLS] 和池化 &#xff08;1&#xff09;[CLS] 的作用 BERT 的输入格式中&#xff0c;每个序列的开头会添加一个特殊的 [CLS] Token&#xff08;Classification Token&#xff09;。它的设计初衷是为分类任务…...

Taro 编译不平不同平台小程序

Taro 提供了针对不同小程序平台的编译命令&#xff0c;主要通过 --type 参数指定目标平台。以下是各平台常用命令及说明&#xff1a; --- ### **一、核心命令格式** 1. **直接使用 taro-cli** bash taro build --type [平台类型] taro dev --type [平台类型] # 开发模式&…...

PHP框架在分布式系统中的应用!

随着互联网业务的快速发展&#xff0c;分布式系统因其高可用性、可扩展性和容错性成为现代应用架构的主流选择。而PHP作为一门成熟的Web开发语言&#xff0c;凭借其简洁的语法、丰富的框架生态和持续的性能优化&#xff0c;逐渐在分布式系统中崭露头角。本文将深入探讨PHP框架在…...

PCB设计实践(十三)PCB设计中差分线间距与线宽设置的深度解析

一、差分信号的基本原理与物理背景 差分信号技术通过两条等幅反相的传输线实现信号传输&#xff0c;其核心优势体现在电磁场耦合的对称性上。根据麦克斯韦方程组的对称解原理&#xff0c;两条线产生的电磁场在远场区域相互抵消&#xff0c;形成以下特性&#xff1a; 1. 共模噪…...

在 Kubernetes 中使用 Docker 实现 GPU 支持的完整方案

目录 在 Kubernetes 中使用 Docker 实现 GPU 支持的完整方案 一、背景说明 二、目标 三、环境准备 四、安装 NVIDIA Container Toolkit&#xff08;nvidia-docker2&#xff09; 五、配置 Docker 支持 NVIDIA Runtime 六、测试 Docker 能否使用 GPU 七、部署 Kubernetes…...

Vision Transformer(ViT)

Vision Transformer&#xff08;ViT&#xff09;是一种将​​Transformer模型​​应用于计算机视觉任务的创新方法&#xff0c;由Google Research团队在2020年提出。它打破了传统卷积神经网络&#xff08;CNN&#xff09;在图像处理中的主导地位&#xff0c;通过全局注意力机制…...

(剪映)字幕实现卡拉OK效果

三种实现方式&#xff1a; 一、剪映自带“模板” 二、剪映自带“动画” 三、使用蒙版特效 具体操作步骤如下 模板的方式 一、模板的方式 1.在时间线轨道区 选中文本 2.在工具栏区中的文本-->模板中选择要实现的效果&#xff0c;左键单击&#xff0c;即可实现效果&am…...

Java结构化并发深度解析:原理、设计与实践

作为Java开发者,当我们需要处理复杂的并发场景时,传统的线程和ExecutorService模型往往导致代码难以维护和调试。Java 21引入的结构化并发(Structured Concurrency)通过创新的设计理念彻底改变了这一局面。本文将深入剖析其实现原理、架构设计,并通过复杂场景案例展示其强大…...

【Linux系列】跨平台安装与配置 Vim 文本编辑器

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

Level1.5算数运算符与赋值运算符

目录 一、算术运算符和赋值运算符 1.1算术运算符 - * / % // ** 1.2.赋值运算符 - * / % // ** 二、等比例缩小&#xff08;变量火柴人案例&#xff09; 三、颜色的三种表达方法取余%运算 1.颜色单词 turtle.pencolor(pink) 2.RGB颜色turtle.pe…...

基于GF域的多进制QC-LDPC误码率matlab仿真,译码采用EMS算法

目录 1.算法仿真效果 2.算法涉及理论知识概要 3.MATLAB核心程序 4.完整算法代码文件获得 1.算法仿真效果 matlab2022a仿真结果如下&#xff08;完整代码运行后无水印&#xff09;&#xff1a; 本课题实现的是四进制QC-LDPC 仿真操作步骤可参考程序配套的操作视频。 2.算…...

CentOS 7 修改锁屏时间为永不

在 CentOS 7 中&#xff0c;默认情况下&#xff0c;系统会在一定时间不活动后自动锁屏。对于某些用户来说&#xff0c;可能希望禁用自动锁屏功能或者将锁屏时间设置为“永不”。本文将介绍如何通过图形界面和命令行两种方式修改 CentOS 7 的锁屏时间&#xff0c;确保系统永不自…...

STM32-ADC模数转换器(7)

对GPIO来说&#xff0c;它只能读取引脚的高低电平&#xff0c;使用了ADC模数转化器之后&#xff0c;就可以对高电平和低电平之间的任意电压进行量化&#xff0c;最终用一个变量来表示&#xff0c;读取这个变量&#xff0c;就能得到引脚输入的具体电压是多少了。 ADC模数转化器…...

前端SSE技术详解:从入门到实战的完整指南

前端SSE技术详解&#xff1a;从入门到实战的完整指南 一、初识SSE&#xff1a;比WebSocket更轻量的选择 很多开发者第一次听说Server-Sent Events&#xff08;SSE&#xff09;时&#xff0c;都会下意识问&#xff1a;“这和WebSocket有什么区别&#xff1f;” 就像选择交通工…...

mac u盘重装mac10.15Catalina系统

我的电脑提mac2017的air 重装过程 (文件夹中间有空格时为 Install\ macOS\ Catalina 才行) &#xff08;有需要的&#xff0c;最好做一下备份&#xff0c;有些东西可以及时找到配置和文件之类的&#xff0c; u盘制作是在mac电脑上操作的) 一、先下载系统镜像文件或自行到官方…...

8051模板移植

8051模板移植 一&#xff0c;新建工程文件二&#xff0c;Keil配置 一&#xff0c;新建工程文件 在工程文件下建立Driver和User 打开Keil&#xff0c;点击扳手选择芯片型号 出现下图情况&#xff0c;选择是&#xff0c;然后会多出一个启动文件&#xff0c;以后有用 二&…...

轻松制作高质量视频,实时生成神器LTX-Video重磅登场!

探索LTX-Video&#xff1a;实时视频生成跨越新高度 在如今这个视觉内容主导的数字时代&#xff0c;视频生成成为推动创意表达的关键。而今天&#xff0c;我们将带您深入探索LTX-Video&#xff0c;一个强大的开源项目&#xff0c;致力于通过尖端技术将视频生成提升到一个全新的…...

两个数组的交集(暴力、set、哈希)

一.题目 给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1&#xff1a; 输入&#xff1a;nums1 [1,2,2,1], nums2 [2,2] 输出&#xff1a;[2]示例 2&#xff1a; 输入&#xf…...

[架构之美]Spring Boot多环境5种方案实现Dev/Test/Prod环境隔离

[架构之美]Spring Boot多环境5种方案实现Dev/Test/Prod环境隔离&#xff08;十六&#xff09; 摘要&#xff1a;本文深入剖析Spring Boot多环境配置的5种实现方案&#xff0c;涵盖YAML分组配置、Maven Profile集成、Kubernetes适配等企业级实践&#xff0c;并附赠配置加密方案…...

LWIP的IP协议笔记

IP协议简介 IP协议是TCP/IP协议族的基石&#xff0c;它为上层提供无连接、不可靠的服务 无连接&#xff1a;指IP通信双方都不长久的维持对方的任何信息。这表示上层协议每次发送数据&#xff0c;都需要明确指出对方的IP地址 不可靠&#xff1a;指IP协议不能把IP数据报准确到…...

matlab介绍while函数

MATLAB 中的 while 语句介绍 在 MATLAB 中&#xff0c;while 语句是一种循环结构&#xff0c;用于在满足特定条件时反复执行一段代码块。与 for 循环不同&#xff0c;while 循环的执行次数是动态的&#xff0c;取决于循环条件是否为真。 语法 while condition% 循环体代码 e…...

每日算法刷题Day2 5.10:leetcode数组1道题3种解法,用时40min

4.LC 旋转矩阵(中等&#xff0c;学习) 面试题 01.07. 旋转矩阵 - 力扣&#xff08;LeetCode&#xff09; 思想: 法一: 额外空间数组来回赋值拷贝 法二: 1.翻转90度得到等式a[j][n-i-1]a[i][j],但是会改变a[j][n-i-1]原始值&#xff0c;再去看该位置变到哪一位置 分析可得,4个…...

【图书管理系统】深度讲解:图书列表展示的后端实现、高内聚低耦合的应用、前端代码讲解

1.约定前后端交互接口 [请求] /book/getListByPage [参数] currentPage1&pageSize10 [响应] 返回封装的result对象对应的Json数据 2. 整体逻辑 2.1 Controller的逻辑 &#xff08;1&#xff09;把接收的参数封装为PageRequest类&#xff0c;里面有属性&#xff1a;curren…...

本地大模型工具深度评测:LM Studio vs Ollama,开发者选型指南

引言 在大语言模型本地化部署的技术浪潮中&#xff0c;隐私保护与成本优化成为核心诉求。LM Studio与Ollama作为两款明星级本地大模型工具&#xff0c;凭借对开源模型的支持能力&#xff0c;成为开发者关注的焦点。本文将从技术架构、应用场景、实操体验三个维度展开深度对比&a…...

天线的PCB设计

目录 天线模块设计的重要性 天线模块的PCB设计 天线模块设计的重要性 当智能手表突然断连、无人机信号飘忽不定——你可能正在经历一场来自天线模块的"无声抗议"。这个隐藏在电子设备深处的关键组件&#xff0c;就像数字世界的隐形信使&#xff0c;用毫米级的精密结…...

《P1226 【模板】快速幂》

题目描述 给你三个整数 a,b,p&#xff0c;求 abmodp。 输入格式 输入只有一行三个整数&#xff0c;分别代表 a,b,p。 输出格式 输出一行一个字符串 a^b mod ps&#xff0c;其中 a,b,p 分别为题目给定的值&#xff0c; s 为运算结果。 输入输出样例 输入 #1复制 2 10 9输…...

推荐一款免费开源工程项目管理系统软件,根据工程项目全过程管理流程开发的OA 办公系统

在当今的工程项目管理领域&#xff0c;许多企业和团队面临着诸多难题。传统的管理方式往往依赖于人工记录和分散的工具&#xff0c;导致项目进度难以实时把控&#xff0c;任务分配不够清晰&#xff0c;合同管理混乱&#xff0c;事件提醒不及时&#xff0c;财务管理缺乏系统性&a…...

AZScreenRecorder最新版:功能强大、操作简便的手机录屏软件

AZScreenRecorder最新版是一款功能强大的手机录屏软件&#xff0c;专为安卓设备设计。它无需ROOT权限&#xff0c;支持无限录制时长&#xff0c;操作简单&#xff0c;录制过程中可以随时暂停&#xff0c;满足不同用户的个性化录屏需求。此外&#xff0c;用户还可以自定义分辨率…...

[sklearn机器学习概述]机器学习-part3

获取数据、数据处理、特征工程后&#xff0c;就可以交给预估器进行机器学习&#xff0c;流程和常用API如下。 1.实例化预估器(估计器)对象(estimator)&#xff0c; 预估器对象很多,都是estimator的子类&#xff08;1&#xff09;用于分类的预估器sklearn.neighbors.KNeighbors…...

[模型选择与调优]机器学习-part4

七 模型选择与调优 1 交叉验证 (1) 保留交叉验证HoldOut HoldOut Cross-validation&#xff08;Train-Test Split&#xff09; 在这种交叉验证技术中&#xff0c;整个数据集被随机地划分为训练集和验证集。根据经验法则&#xff0c;整个数据集的近70%被用作训练集&#xff…...

PyTorch API 1 - 概述、数学运算、nn、实用工具、函数、张量

文章目录 torch张量创建操作索引、切片、连接与变异操作 加速器生成器随机采样原地随机采样准随机采样 序列化并行计算局部禁用梯度计算数学运算常量逐点运算归约操作比较运算频谱操作其他操作BLAS 和 LAPACK 运算遍历操作遍历操作遍历操作遍历操作遍历操作遍历操作遍历操作遍历…...

如何在mac上使用便利贴

可以在 App Store 下载便利贴应用实现在电脑上贴便条的效果。 以 「桌面便利贴」这款应用为例&#xff0c;创建的便利贴会像桌面上的文件一样展示在桌面上&#xff0c;随时可以查看。还可以修改便笺的颜色、透明度、字体、高亮等等。 我比较喜欢的功能是将便签固定在所有窗口的…...

Linux——Mysql索引和事务

目录 一&#xff0c;Mysql索引介绍 1&#xff0c;索引概述 1&#xff0c;索引的优点 2&#xff0c;索引的缺点 2&#xff0c;索引作用 3&#xff0c;索引分类 普通索引 唯一索引 主键索引 组合索引 全文索引 4&#xff0c;查看索引 5&#xff0c;删除索引 6&…...

vim 查看复杂的宏扩展

在一些复杂项目中&#xff0c;使用宏可以简化代码。但是对于刚接触项目的人来说&#xff0c;分析层层嵌套的宏&#xff0c;是件头疼的事情。 使用 vim 的多窗口功能&#xff0c;可以为此提供一些帮助。 如下图&#xff0c;分析4层嵌套的宏&#xff0c;DEFINE_I440FX_MACHINE -…...

【计算机视觉】OpenCV项目实战:基于OpenCV的图像分割技术深度解析与实践指南

基于OpenCV的图像分割技术深度解析与实践指南 项目概述与技术背景项目核心特点传统分割算法分类 环境配置与项目结构系统要求安装步骤项目结构解析 核心算法实现解析1. 阈值分割&#xff08;Otsu方法&#xff09;2. Canny边缘检测3. 分水岭算法 实战应用指南1. 基础分割流程2. …...

线性表-顺序表(Sequential List)

1 线性表 1.1 顺序表&#xff08;Sequential List&#xff09; 顺序表并不难理解&#xff0c;主要是知道顺序表是在内存中连续存储的一段数据&#xff0c;知道这个后&#xff0c;相应的算法也就非常简单了。 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的…...

《用MATLAB玩转游戏开发:从零开始打造你的数字乐园》基础篇(2D图形交互)-俄罗斯方块:用旋转矩阵打造经典

《用MATLAB玩转游戏开发&#xff1a;从零开始打造你的数字乐园》基础篇&#xff08;2D图形交互&#xff09;-&#x1f3ae; 俄罗斯方块&#xff1a;用旋转矩阵打造经典 &#x1f9ca; 大家好&#xff01;今天我将带大家用MATLAB实现经典的俄罗斯方块游戏。我们将从数学原理出发…...

通过user-agent来源判断阻止爬虫访问网站,并防止生成[ error ] NULL日志

一、TP5.0通过行为&#xff08;Behavior&#xff09;拦截爬虫并避免生成 [ error ] NULL 错误日志 1. 创建行为类&#xff08;拦截爬虫&#xff09; 在 application/common/behavior 目录下新建BlockBot.php &#xff0c;用于识别并拦截爬虫请求&#xff1a; <?php name…...

微服务的“迷宫” - 我们为何需要服务网格?

微服务的“迷宫” - 我们为何需要服务网格? 你好!欢迎来到我们的服务网格探索之旅。近年来,“微服务架构”无疑是软件开发领域最热门的词汇之一。它将庞大的单体应用拆分成一组小而独立的、可以独立开发、部署和扩展的服务单元,带来了前所未有的敏捷性和弹性。开发团队可以…...

Ubuntu 安装 HAProxy

HAProxy 是什么 HAProxy&#xff08;High Availability Proxy&#xff09; 是一个 高性能、高可用的 TCP 和 HTTP 负载均衡器与代理服务器。 HAProxy 的特点 特性说明支持协议HTTP、HTTPS、TCP高性能使用 C 语言编写&#xff0c;性能极高高可用与 Keepalived 配合可实现主备健…...