教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」AlgoNote中 0015. 三数之和 题解的完整展开版围绕这道经典的「数组、双指针、排序」中等题系统讲解从暴力枚举到排序 对撞指针的优化路径、去重细节、复杂度分析并结合仓库中的双指针理论基础与系列变体题目最接近的三数之和、四数之和等给出实战扩展。读完本文你将掌握「三数之和」的标准解法及其去重原理并能在 两数之和 的基础上独立推导四数之和等同类问题。1. 题目概述题目链接0015. 三数之和 - 力扣标签数组、双指针、排序难度中等1.1 题目描述给定一个整数数组nums判断nums中是否存在三个元素a、b、c满足a b c 0。要求找出所有满足要求且不重复的三元组。1.2 数据范围与约束3 ≤ nums.length ≤ 3000-10^5 ≤ nums[i] ≤ 10^5这意味着数组最长可达 3000 个元素暴力三重循环在最坏情况下需要约3000³ ≈ 2.7 × 10^10次运算必然超时因此必须把复杂度优化到平方级别以下。1.3 示例示例 1输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]]示例 2输入nums [0,1,1] 输出[]注意示例 1 中nums有两个-1但最终只输出一个[-1, 0, 1]和[-1, -1, 2]可见去重防止相同数值组合重复输出是本体的核心难点之一。2. 思路演进从暴力枚举到对撞指针2.1 暴力枚举O(n³)最直观的做法是三重循环枚举所有下标组合(i, j, k)判断nums[i] nums[j] nums[k] 0。但该做法存在两个问题时间复杂度过高总时间复杂度为O(n³)在n 3000时不可接受去重困难即使找到满足条件的三元组还需要额外处理重复组合实现复杂且容易出错。正如 0015. 三数之和 原文所述「直接三重遍历查找 a、b、c 的时间复杂度是 O(n³)我们可以通过一些操作来降低复杂度」。2.2 核心优化排序 对撞指针优化路径分两步排序O(n log n)先对数组升序排序。排序之后按顺序固定第一个元素a再在a右侧区间用双指针查找剩余两个数时天然处于升序序列上便于利用「单调性」控制指针移动同时保证找到的三元组按序去重对撞指针O(n)固定a之后left指向a的下一个位置right指向数组末尾两者相向移动。根据三数之和与0的大小关系决定移动方向每一轮移动都能排除大量无效组合。关于对撞指针的定义仓库 双指针基础 一节给出如下解释对撞指针即用两个指针left和right分别指向序列的首尾left向右、right向左移动直到两指针相遇left right或满足特定条件。其中还给出了对撞指针的通用模板初始化左右指针后while left right循环内根据条件分别执行left 1或right - 1。三数之和正是这一模板在「有序数组中查找特定元素组合」场景下的经典应用见 对撞指针适用场景。3. 解题思路排序 对撞指针详解3.1 算法步骤对数组nums进行升序排序时间复杂度为O(n × log n)第一重循环遍历固定元素a下标i去重固定元素若i 0且nums[i] nums[i - 1]说明当前值与上一个已处理过的固定值相同直接continue避免产生重复三元组初始化对撞指针left i 1指向a的下一个位置right n - 1指向末尾在while left right的循环中去重左指针若left已越过初始位置left i 1且nums[left] nums[left - 1]则left 1跳过重复值去重右指针若right已小于末尾right n - 1且nums[right 1] nums[right]则right - 1跳过重复值然后判断三数之和若nums[i] nums[left] nums[right] 0找到一个解加入答案数组并同时left 1、right - 1继续查找下一组若nums[i] nums[left] nums[right] 0说明nums[right]值太大将right左移right - 1使总和变小若nums[i] nums[left] nums[right] 0说明nums[left]值太小将left右移left 1使总和变大。3.2 为什么对撞指针能保证不漏解在升序数组的[left, right]区间内nums[left]是最小值、nums[right]是最大值。当三数之和大于0时由于nums[i]固定、nums[left]已是最小唯一能让总和减小的方向只有让right左移同理当三数之和小于0时唯一能让总和增大的方向只有让left右移。每一步都基于「单调性」做出唯一正确的决策因此不会跳过任何可能的组合这正是双指针方法能够将暴力枚举从O(n³)降至O(n²)的核心原因。4. 完整代码与逐行注释以下代码来自 0015. 三数之和 原文并补充了逐行注释class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: n len(nums) nums.sort() # 1. 排序保证后续查找有序、方便去重 ans [] # 2. 答案数组 for i in range(n): # 3. 第一重循环固定元素 a nums[i] # 固定元素去重跳过与上一个相同的值 if i 0 and nums[i] nums[i - 1]: continue left i 1 # 4. 左指针指向 a 的下一个位置 right n - 1 # 5. 右指针指向末尾 while left right: # 左指针去重越过与上一个相同的值 while left right and left i 1 and nums[left] nums[left - 1]: left 1 # 右指针去重越过与下一个相同的值 while left right and right n - 1 and nums[right 1] nums[right]: right - 1 if left right and nums[i] nums[left] nums[right] 0: # 6. 找到一组解加入答案并同时收缩区间 ans.append([nums[i], nums[left], nums[right]]) left 1 right - 1 elif nums[i] nums[left] nums[right] 0: # 7. 总和过大右指针左移 right - 1 else: # 8. 总和过小左指针右移 left 1 return ans4.1 去重细节剖析三处去重是本题能否 AC 的关键固定元素去重nums[i] nums[i - 1]同一固定值a只处理一次。例如示例 1 中两个-1只用第一个-1作为固定值查找第二个直接跳过左指针去重left i 1 and nums[left] nums[left - 1]当left不是初始位置且与上一个值相同时右移跳过避免同一固定值下重复输出相同组合右指针去重right n - 1 and nums[right 1] nums[right]对称地处理右指针方向。如果去掉这三处去重例如输入[-1, -1, -1, 0, 1, 1, 1]会输出多组[-1, 0, 1]不满足题目「不重复的三元组」的要求。4.2 复杂度分析时间复杂度O(n²)。外层循环遍历i需要O(n)内层对撞指针每轮最多遍历n个元素总计O(n²)排序需要O(n log n)整体仍为O(n²)空间复杂度O(n)。主要为答案数组所占空间最坏情况下三元组数量级为O(n²)的上限之内文档标注为O(n)此外排序、指针与去重比较仅使用常数级额外空间。5. 仓库中的理论支撑与实战位置5.1 双指针理论基础三数之和属于对撞指针碰撞指针的典型例题。在 双指针基础 中对撞指针被定义为左右两端相向移动的指针模式其典型适用场景包括查找有序数组中特定元素组合如二分查找、两数之和等字符串或数组反转、回文判断等。该文档将三数之和直接列为对撞指针的练习题目之一与 0344. 反转字符串、0345. 反转字符串中的元音字母、0027. 移除元素、0080. 删除有序数组中的重复项 II 等共同构成双指针练习清单适合按顺序巩固。5.2 在题库体系中的位置三数之和在「算法通关手册」的题目体系中具有高频地位出现在 高频面试题 100 题清单 与 高频面试题 200 题清单 中标注为「数组、双指针、排序、中等」收录于 分类题目清单 的「双指针」分类下是该分类的核心例题在 完整题解清单 中按题号 0015 收录。从清单结构可以看出本题与两数之和、四数之和共同构成「双指针求解 N 数之和」的完整知识链。6. 同系列变体与扩展练习掌握了三数之和后可以顺藤摸瓜解决仓库中收录的一整族变体题目6.1 两数之和前置基础0001. 两数之和 是本题的二维前身仓库给出了两种解法暴力枚举两重循环时间复杂度O(n²)哈希表遍历时在字典中查找target - nums[i]时间复杂度降至O(n)。注意两数之和要求返回下标且题目保证只有唯一解而三数之和要求返回数值组合且必须去重因此三数之和选择了「排序 双指针」而非哈希表路线——排序天然解决去重双指针则把查找两数的过程压到O(n)。6.2 最接近的三数之和0016. 最接近的三数之和 把「等于 0」放宽为「与 target 最接近」解法仍为排序 对撞指针用ans记录当前最接近的三数和每次计算nums[i] nums[left] nums[right]与target的差值差值更小则更新ans总和小于target时left右移否则right左移。因为不要求去重实现上比本题更简单时间复杂度同为O(n²)。6.3 四数之和0018. 四数之和 将问题扩展为四个数解法与本题完全同构排序后两重循环固定前两个元素a、b再用对撞指针查找c、d。固定元素与指针同样需要三层去重。时间复杂度升级为O(n³)——每增加一个固定维度时间复杂度就乘一次n这也从侧面印证了「双指针只能省去一重遍历」这一规律。6.4 较小的三数之和0259. 较小的三数之和 统计「三数之和小于 target」的三元组个数标签为「数组、双指针、二分查找、排序」是在三数之和框架上叠加计数逻辑的变体。6.5 三数之和的多种可能0923. 三数之和的多种可能 由于元素值域较小0 ≤ arr[i] ≤ 100采用「哈希表统计频次 按值枚举」的方案用Counter统计每个数值出现次数枚举(i, j, k)组合并利用组合数公式三个相同取C(count[i], 3)、两个相同取C(count[i], 2) × count[k]、全不同取三者乘积计算方案数最后对10^9 7取模。6.6 进阶清单除上述变体外仓库的 双指针题目列表 还收录了剑指 Offer 同题 LCR 007. 三数之和标签同为「数组、双指针、排序」可作为同题不同题号的交叉练习。7. 总结与刷题建议三数之和的核心方法论可以提炼为一句口诀「排序定一双指针扫二三处去重」。排序为双指针提供单调性基础同时天然支持去重定一外层循环固定一个元素将问题降维为「有序数组中的两数之和」扫二内层对撞指针以O(n)完成两数查找整体复杂度O(n²)去重固定元素、左指针、右指针三处都要跳过重复值保证三元组不重复。建议的练习顺序为先完成 两数之和 II - 输入有序数组对撞指针入门再攻克 0015. 三数之和 本体随后按 0016. 最接近的三数之和 → 0018. 四数之和 → 0259. 较小的三数之和 → 0923. 三数之和的多种可能 的顺序逐层递进即可系统掌握「N 数之和」家族的排序 双指针解法。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 15. 三数之和3Sum题解排序 双指针的 N 数之和通法解析LeetCode 15. 三数之和3Sum题解排序 双指针的 N 数之和通法解析 导读 三数之和3Sum是 LeetCode 面试高频题要求在一文档教程知识库LeetCode 0075 颜色分类题解双指针一趟扫描实现荷兰国旗三色排序AlgoNote 算法通关手册实战解析LeetCode 0075 颜色分类题解双指针一趟扫描实现荷兰国旗三色排序AlgoNote 算法通关手册实战解析 本篇题解基于 AlgoNote「算法通关教程文档知识库告别网盘限速烦恼九大平台直链下载终极解决方案告别网盘限速烦恼九大平台直链下载终极解决方案 还在为百度网盘、阿里云盘等主流云存储服务的下载限速而烦恼吗LinkSwift网盘直链下载助手为你提供 免费、快教程文档知识库上一篇mdserver-web备份恢复策略确保服务器数据万无一失下一篇7个实用技巧Mermaid.js状态图绘制复杂系统状态转换的终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 0015 三数之和：排序 + 对撞指针全解（AlgoNote 算法通关手册）
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」AlgoNote中 0015. 三数之和 题解的完整展开版围绕这道经典的「数组、双指针、排序」中等题系统讲解从暴力枚举到排序 对撞指针的优化路径、去重细节、复杂度分析并结合仓库中的双指针理论基础与系列变体题目最接近的三数之和、四数之和等给出实战扩展。读完本文你将掌握「三数之和」的标准解法及其去重原理并能在 两数之和 的基础上独立推导四数之和等同类问题。1. 题目概述题目链接0015. 三数之和 - 力扣标签数组、双指针、排序难度中等1.1 题目描述给定一个整数数组nums判断nums中是否存在三个元素a、b、c满足a b c 0。要求找出所有满足要求且不重复的三元组。1.2 数据范围与约束3 ≤ nums.length ≤ 3000-10^5 ≤ nums[i] ≤ 10^5这意味着数组最长可达 3000 个元素暴力三重循环在最坏情况下需要约3000³ ≈ 2.7 × 10^10次运算必然超时因此必须把复杂度优化到平方级别以下。1.3 示例示例 1输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]]示例 2输入nums [0,1,1] 输出[]注意示例 1 中nums有两个-1但最终只输出一个[-1, 0, 1]和[-1, -1, 2]可见去重防止相同数值组合重复输出是本体的核心难点之一。2. 思路演进从暴力枚举到对撞指针2.1 暴力枚举O(n³)最直观的做法是三重循环枚举所有下标组合(i, j, k)判断nums[i] nums[j] nums[k] 0。但该做法存在两个问题时间复杂度过高总时间复杂度为O(n³)在n 3000时不可接受去重困难即使找到满足条件的三元组还需要额外处理重复组合实现复杂且容易出错。正如 0015. 三数之和 原文所述「直接三重遍历查找 a、b、c 的时间复杂度是 O(n³)我们可以通过一些操作来降低复杂度」。2.2 核心优化排序 对撞指针优化路径分两步排序O(n log n)先对数组升序排序。排序之后按顺序固定第一个元素a再在a右侧区间用双指针查找剩余两个数时天然处于升序序列上便于利用「单调性」控制指针移动同时保证找到的三元组按序去重对撞指针O(n)固定a之后left指向a的下一个位置right指向数组末尾两者相向移动。根据三数之和与0的大小关系决定移动方向每一轮移动都能排除大量无效组合。关于对撞指针的定义仓库 双指针基础 一节给出如下解释对撞指针即用两个指针left和right分别指向序列的首尾left向右、right向左移动直到两指针相遇left right或满足特定条件。其中还给出了对撞指针的通用模板初始化左右指针后while left right循环内根据条件分别执行left 1或right - 1。三数之和正是这一模板在「有序数组中查找特定元素组合」场景下的经典应用见 对撞指针适用场景。3. 解题思路排序 对撞指针详解3.1 算法步骤对数组nums进行升序排序时间复杂度为O(n × log n)第一重循环遍历固定元素a下标i去重固定元素若i 0且nums[i] nums[i - 1]说明当前值与上一个已处理过的固定值相同直接continue避免产生重复三元组初始化对撞指针left i 1指向a的下一个位置right n - 1指向末尾在while left right的循环中去重左指针若left已越过初始位置left i 1且nums[left] nums[left - 1]则left 1跳过重复值去重右指针若right已小于末尾right n - 1且nums[right 1] nums[right]则right - 1跳过重复值然后判断三数之和若nums[i] nums[left] nums[right] 0找到一个解加入答案数组并同时left 1、right - 1继续查找下一组若nums[i] nums[left] nums[right] 0说明nums[right]值太大将right左移right - 1使总和变小若nums[i] nums[left] nums[right] 0说明nums[left]值太小将left右移left 1使总和变大。3.2 为什么对撞指针能保证不漏解在升序数组的[left, right]区间内nums[left]是最小值、nums[right]是最大值。当三数之和大于0时由于nums[i]固定、nums[left]已是最小唯一能让总和减小的方向只有让right左移同理当三数之和小于0时唯一能让总和增大的方向只有让left右移。每一步都基于「单调性」做出唯一正确的决策因此不会跳过任何可能的组合这正是双指针方法能够将暴力枚举从O(n³)降至O(n²)的核心原因。4. 完整代码与逐行注释以下代码来自 0015. 三数之和 原文并补充了逐行注释class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: n len(nums) nums.sort() # 1. 排序保证后续查找有序、方便去重 ans [] # 2. 答案数组 for i in range(n): # 3. 第一重循环固定元素 a nums[i] # 固定元素去重跳过与上一个相同的值 if i 0 and nums[i] nums[i - 1]: continue left i 1 # 4. 左指针指向 a 的下一个位置 right n - 1 # 5. 右指针指向末尾 while left right: # 左指针去重越过与上一个相同的值 while left right and left i 1 and nums[left] nums[left - 1]: left 1 # 右指针去重越过与下一个相同的值 while left right and right n - 1 and nums[right 1] nums[right]: right - 1 if left right and nums[i] nums[left] nums[right] 0: # 6. 找到一组解加入答案并同时收缩区间 ans.append([nums[i], nums[left], nums[right]]) left 1 right - 1 elif nums[i] nums[left] nums[right] 0: # 7. 总和过大右指针左移 right - 1 else: # 8. 总和过小左指针右移 left 1 return ans4.1 去重细节剖析三处去重是本题能否 AC 的关键固定元素去重nums[i] nums[i - 1]同一固定值a只处理一次。例如示例 1 中两个-1只用第一个-1作为固定值查找第二个直接跳过左指针去重left i 1 and nums[left] nums[left - 1]当left不是初始位置且与上一个值相同时右移跳过避免同一固定值下重复输出相同组合右指针去重right n - 1 and nums[right 1] nums[right]对称地处理右指针方向。如果去掉这三处去重例如输入[-1, -1, -1, 0, 1, 1, 1]会输出多组[-1, 0, 1]不满足题目「不重复的三元组」的要求。4.2 复杂度分析时间复杂度O(n²)。外层循环遍历i需要O(n)内层对撞指针每轮最多遍历n个元素总计O(n²)排序需要O(n log n)整体仍为O(n²)空间复杂度O(n)。主要为答案数组所占空间最坏情况下三元组数量级为O(n²)的上限之内文档标注为O(n)此外排序、指针与去重比较仅使用常数级额外空间。5. 仓库中的理论支撑与实战位置5.1 双指针理论基础三数之和属于对撞指针碰撞指针的典型例题。在 双指针基础 中对撞指针被定义为左右两端相向移动的指针模式其典型适用场景包括查找有序数组中特定元素组合如二分查找、两数之和等字符串或数组反转、回文判断等。该文档将三数之和直接列为对撞指针的练习题目之一与 0344. 反转字符串、0345. 反转字符串中的元音字母、0027. 移除元素、0080. 删除有序数组中的重复项 II 等共同构成双指针练习清单适合按顺序巩固。5.2 在题库体系中的位置三数之和在「算法通关手册」的题目体系中具有高频地位出现在 高频面试题 100 题清单 与 高频面试题 200 题清单 中标注为「数组、双指针、排序、中等」收录于 分类题目清单 的「双指针」分类下是该分类的核心例题在 完整题解清单 中按题号 0015 收录。从清单结构可以看出本题与两数之和、四数之和共同构成「双指针求解 N 数之和」的完整知识链。6. 同系列变体与扩展练习掌握了三数之和后可以顺藤摸瓜解决仓库中收录的一整族变体题目6.1 两数之和前置基础0001. 两数之和 是本题的二维前身仓库给出了两种解法暴力枚举两重循环时间复杂度O(n²)哈希表遍历时在字典中查找target - nums[i]时间复杂度降至O(n)。注意两数之和要求返回下标且题目保证只有唯一解而三数之和要求返回数值组合且必须去重因此三数之和选择了「排序 双指针」而非哈希表路线——排序天然解决去重双指针则把查找两数的过程压到O(n)。6.2 最接近的三数之和0016. 最接近的三数之和 把「等于 0」放宽为「与 target 最接近」解法仍为排序 对撞指针用ans记录当前最接近的三数和每次计算nums[i] nums[left] nums[right]与target的差值差值更小则更新ans总和小于target时left右移否则right左移。因为不要求去重实现上比本题更简单时间复杂度同为O(n²)。6.3 四数之和0018. 四数之和 将问题扩展为四个数解法与本题完全同构排序后两重循环固定前两个元素a、b再用对撞指针查找c、d。固定元素与指针同样需要三层去重。时间复杂度升级为O(n³)——每增加一个固定维度时间复杂度就乘一次n这也从侧面印证了「双指针只能省去一重遍历」这一规律。6.4 较小的三数之和0259. 较小的三数之和 统计「三数之和小于 target」的三元组个数标签为「数组、双指针、二分查找、排序」是在三数之和框架上叠加计数逻辑的变体。6.5 三数之和的多种可能0923. 三数之和的多种可能 由于元素值域较小0 ≤ arr[i] ≤ 100采用「哈希表统计频次 按值枚举」的方案用Counter统计每个数值出现次数枚举(i, j, k)组合并利用组合数公式三个相同取C(count[i], 3)、两个相同取C(count[i], 2) × count[k]、全不同取三者乘积计算方案数最后对10^9 7取模。6.6 进阶清单除上述变体外仓库的 双指针题目列表 还收录了剑指 Offer 同题 LCR 007. 三数之和标签同为「数组、双指针、排序」可作为同题不同题号的交叉练习。7. 总结与刷题建议三数之和的核心方法论可以提炼为一句口诀「排序定一双指针扫二三处去重」。排序为双指针提供单调性基础同时天然支持去重定一外层循环固定一个元素将问题降维为「有序数组中的两数之和」扫二内层对撞指针以O(n)完成两数查找整体复杂度O(n²)去重固定元素、左指针、右指针三处都要跳过重复值保证三元组不重复。建议的练习顺序为先完成 两数之和 II - 输入有序数组对撞指针入门再攻克 0015. 三数之和 本体随后按 0016. 最接近的三数之和 → 0018. 四数之和 → 0259. 较小的三数之和 → 0923. 三数之和的多种可能 的顺序逐层递进即可系统掌握「N 数之和」家族的排序 双指针解法。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 15. 三数之和3Sum题解排序 双指针的 N 数之和通法解析LeetCode 15. 三数之和3Sum题解排序 双指针的 N 数之和通法解析 导读 三数之和3Sum是 LeetCode 面试高频题要求在一文档教程知识库LeetCode 0075 颜色分类题解双指针一趟扫描实现荷兰国旗三色排序AlgoNote 算法通关手册实战解析LeetCode 0075 颜色分类题解双指针一趟扫描实现荷兰国旗三色排序AlgoNote 算法通关手册实战解析 本篇题解基于 AlgoNote「算法通关教程文档知识库告别网盘限速烦恼九大平台直链下载终极解决方案告别网盘限速烦恼九大平台直链下载终极解决方案 还在为百度网盘、阿里云盘等主流云存储服务的下载限速而烦恼吗LinkSwift网盘直链下载助手为你提供 免费、快教程文档知识库上一篇mdserver-web备份恢复策略确保服务器数据万无一失下一篇7个实用技巧Mermaid.js状态图绘制复杂系统状态转换的终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考