LeetCode 热题100 15. 三数之和
LeetCode 热题100 | 15. 三数之和
大家好,今天我们来解决一道经典的算法题——三数之和。这道题在 LeetCode 上被标记为中等难度,要求我们从一个整数数组中找到所有不重复的三元组,使得三元组的和为 0。下面我将详细讲解解题思路,并附上 Python 代码实现。
题目描述
给定一个整数数组 nums,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k,同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
示例:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解题思路
这道题的核心是找到所有满足条件的三元组,同时避免重复。我们可以通过排序数组和双指针法来高效地解决这个问题。
核心思想
-
排序数组:
- 将数组排序,方便后续使用双指针法。
-
遍历数组:
- 固定一个数
nums[i],然后在剩下的数组中使用双指针法寻找两个数nums[left]和nums[right],使得nums[i] + nums[left] + nums[right] == 0。
- 固定一个数
-
双指针法:
- 初始化
left = i + 1,right = len(nums) - 1。 - 如果
nums[i] + nums[left] + nums[right] < 0,则left右移。 - 如果
nums[i] + nums[left] + nums[right] > 0,则right左移。 - 如果
nums[i] + nums[left] + nums[right] == 0,则找到一个三元组,记录下来,并跳过重复的元素。
- 初始化
-
去重:
- 在遍历过程中,跳过重复的
nums[i]、nums[left]和nums[right],避免重复的三元组。
- 在遍历过程中,跳过重复的
代码实现
def threeSum(nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort() # 排序数组result = [] # 存储结果for i in range(len(nums) - 2): # 遍历数组,固定 nums[i]if i > 0 and nums[i] == nums[i - 1]: # 跳过重复的 nums[i]continueleft, right = i + 1, len(nums) - 1 # 初始化双指针while left < right:total = nums[i] + nums[left] + nums[right] # 计算三数之和if total < 0:left += 1 # 和小于 0,左指针右移elif total > 0:right -= 1 # 和大于 0,右指针左移else:result.append([nums[i], nums[left], nums[right]]) # 找到一个三元组# 跳过重复的 nums[left] 和 nums[right]while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1return result
代码解析
-
排序数组:
- 将数组排序,方便后续使用双指针法。
-
遍历数组:
- 固定一个数
nums[i],然后在剩下的数组中使用双指针法寻找两个数nums[left]和nums[right]。
- 固定一个数
-
双指针法:
- 初始化
left = i + 1,right = len(nums) - 1。 - 根据三数之和的大小,移动
left或right指针。
- 初始化
-
去重:
- 在遍历过程中,跳过重复的
nums[i]、nums[left]和nums[right],避免重复的三元组。
- 在遍历过程中,跳过重复的
复杂度分析
- 时间复杂度:O(n²),其中 n 是数组的长度。排序的时间复杂度为 O(n log n),双指针法的时间复杂度为 O(n²)。
- 空间复杂度:O(1),只使用了常数个额外空间。
示例运行
示例 1
# 输入:nums = [-1,0,1,2,-1,-4]
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums)) # 输出: [[-1, -1, 2], [-1, 0, 1]]
示例 2
# 输入:nums = [0,1,1]
nums = [0, 1, 1]
print(threeSum(nums)) # 输出: []
示例 3
# 输入:nums = [0,0,0]
nums = [0, 0, 0]
print(threeSum(nums)) # 输出: [[0, 0, 0]]
总结
通过排序数组和双指针法,我们可以高效地找到所有满足条件的三元组,并避免重复。这种方法的时间复杂度为 O(n²),能够处理较大的输入规模。希望这篇题解对你有帮助!如果还有其他问题,欢迎继续提问!
关注我,获取更多算法题解和编程技巧!
相关文章:
LeetCode 热题100 15. 三数之和
LeetCode 热题100 | 15. 三数之和 大家好,今天我们来解决一道经典的算法题——三数之和。这道题在 LeetCode 上被标记为中等难度,要求我们从一个整数数组中找到所有不重复的三元组,使得三元组的和为 0。下面我将详细讲解解题思路,…...
网络空间安全(1)web应用程序的发展历程
前言 Web应用程序的发展历程是一部技术创新与社会变革交织的长卷,从简单的文档共享系统到如今复杂、交互式、数据驱动的平台,经历了多个重要阶段。 一、起源与初期发展(1989-1995年) Web的诞生: 1989年,欧洲…...
ABAQUS功能梯度材料FGM模型
功能梯度材料(FGM)作为一种新型复合材料,通过材料内部成分或微观结构的梯度变化,优化特定性能适应复杂环境,被广泛应用于高温防护、结构优化、生物医学、光电设备等领域。本案例介绍在ABAQUS内建立功能梯度材料模型。 …...
自适应增强技术
1. 传统图像处理中的自适应增强(如CLAHE) 难度:⭐容易 实现方式:调用成熟的库(如OpenCV)函数即可完成。 示例代码(CLAHE增强): <PYTHON> import cv2# 输入灰度或彩…...
虚拟项目:一个好用的工具平台
在当今数字化的时代,虚拟项目如雨后春笋般涌现,为人们提供了诸多便捷且充满机遇的选择。以下将为大家详细介绍几种颇具特色的虚拟项目,包括书签、资源站、题库、虚拟商城、专栏、证件照以及分站搭建等,一起来了解它们各自的独特之…...
MySQL 和 Elasticsearch 之间的数据同步
MySQL 和 Elasticsearch 之间的数据同步是常见的需求,通常用于将结构化数据从关系型数据库同步到 Elasticsearch 以实现高效的全文搜索、聚合分析和实时查询。以下是几种常用的同步方案及其实现方法: 1. 应用层双写(双写模式) 原…...
PS裁剪工具
裁剪: 多张图同一标准裁剪:裁剪–》前面的图像–》选择其他图像–》 确定 选区–》裁剪工具–》确定:选区制作矩形裁剪 裁剪–》拉直 裁剪–》内容识别:当裁剪大于图片大小,会自动填充空白区域 (栅格化图层…...
[Web 安全] PHP 反序列化漏洞 —— PHP 序列化 反序列化
关注这个专栏的其他相关笔记:[Web 安全] 反序列化漏洞 - 学习笔记-CSDN博客 0x01:PHP 序列化 — Serialize 序列化就是将对象的状态信息转化为可以存储或传输的形式的过程,在 PHP 中,通常使用 serialize() 函数来完成序列化的操作…...
QT入门--QMainWindow
从上向下依次是菜单栏,工具栏,铆接部件(浮动窗口),状态栏,中心部件 菜单栏 创建菜单栏 QMenuBar* mybar1 menuBar(); 将菜单栏放到窗口中 setMenuBar(mybar1); 创建菜单 QMenu *myfilemenu mybar1-…...
C++ | 高级教程 | 信号处理
👻 概念 信号 —— 操作系统传给进程的中断,会提早终止程序有些信号不能被程序捕获,有些则可以被捕获,并基于信号采取适当的动作 信号描述SIGABRT程序的异常终止,如调用 abortSIGFPE错误的算术运算,比如除…...
最新前端框架选型对比与建议(React/Vue/Svelte/Angular)
前端框架选型对比与建议(React/Vue/Svelte/Angular) 一、核心框架技术特性对比(基于最新版本) 维度React 19 25Vue 3.5 12Svelte 5 25Angular 19 5核心理念函数式编程、JSX语法、虚拟DOM渐进式框架、组合式API、模板语法编译时框…...
游戏引擎学习第123天
仓库:https://gitee.com/mrxiao_com/2d_game_3 黑板:线程同步/通信 目标是从零开始编写一个完整的游戏。我们不使用引擎,也不依赖任何库,完全自己编写游戏所需的所有代码。我们做这个节目不仅是为了教育目的,同时也是因为编程本…...
计算机网络:从底层原理到前沿应用,解锁数字世界的连接密码
计算机网络:从底层原理到前沿应用,解锁数字世界的连接密码 在信息如洪流般奔涌的时代,计算机网络宛如无形的脉络,贯穿于我们生活的每一个角落。它不仅是数据传输的通道,更是连接全球、驱动创新的核心力量。从日常的网络…...
grafana K6压测
文章目录 install and runscript.jsoptions最佳实践 report 解析 https://grafana.com/docs/k6/latest/get-started install and run install # mac brew install k6当前目录下生成压测脚本 # create file script.js k6 new [filename] # create file ‘script.js’ in …...
Vue的组合式API和选项式API有什么区别
Vue3的组合式API(Composition API)和选项式API(Options API)是两种不同的组件编写方式,主要区别如下: 1. 代码组织方式 选项式API: 按照选项(如data、methods、computed等࿰…...
ubuntu 安全策略(等保)
windows 三个帐号屏保设置组策略,密码超时次数/审计记录; linux 应具有登录失败处理功能,应配置并启用结束会话、限制非法登录次数和当登录连接超时自动退出等相关措施。 1、在系统中新建测试用户,使用此用户登录时多次输入错误密码&…...
c/c++蓝桥杯经典编程题100道(22)最短路径问题
最短路径问题 ->返回c/c蓝桥杯经典编程题100道-目录 目录 最短路径问题 一、题型解释 二、例题问题描述 三、C语言实现 解法1:Dijkstra算法(正权图,难度★★) 解法2:Bellman-Ford算法(含负权边&a…...
AI工具集合
设计相关 1. mastrtgo(暂时免费) :可以根据自然语言生成UI设计稿和前端代码 MasterGo 莫高设计 - AI 时代的数字界面生产平台 2. reddy.ai(暂时免费): 国外类似mastrtgo的平台 Readdy 3. midjourney (…...
CSDN 博客:CC++ 内存管理详解
CSDN 博客:C/C 内存管理详解 在软件开发过程中,内存管理是一个非常重要的环节。对于 C 和 C 这两种编程语言,它们都拥有独特的内存管理机制,理解这些机制对于编写高效、健壮的程序至关重要。本文将详细讲解 C/C 内存管理相关的内…...
表单制作代码,登录动画背景前端模板
炫酷动效登录页 引言 在网页设计中,按钮是用户交互的重要元素之一。一个炫酷的按钮特效不仅能提升用户体验,还能为网页增添独特的视觉吸引力。今天,我们将通过CSS来实现一个“表单制作代码,登录动画背景前端模板”。该素材呈现了数据符号排版显示出人形的动画效果,新颖有…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
