LeetCode 3Sum三数之和题解全析暴力枚举、哈希表与双指针三方案对比【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 15「三数之和」3Sum问题展开完整讲解从暴力枚举到哈希表、再到最优双指针的三种解法覆盖排序去重、指针收缩与频次计数等核心技巧。文章以 articles/three-integer-sum.md 为骨架结合本仓库在 C、C、Go、Java、Python、TypeScript 等 14 种语言中的真实实现见 c/0015-3sum.c、cpp/0015-3sum.cpp、python/0015-3sum.py 等进行源码级印证。读完本文你将掌握三类解法的推导逻辑、去重边界条件、复杂度差异以及面试与刷题中最高频的易错点。问题定义与前置知识问题描述给定一个整数数组nums返回所有和为0且不重复的三元组[nums[i], nums[j], nums[k]]要求i j k。例如输入nums [-1, 0, 1, 2, -1, -4]合法输出为[[-1, -1, 2], [-1, 0, 1]][-1, 0, 1]与[0, 1, -1]视为同一个三元组不能重复输出。动手之前原文档要求你至少熟悉以下四项基础能力排序Sorting对数组排序是高效去重与双指针技术的前提双指针Two pointers最优解法依赖双指针在有序数组中寻找满足目标和的数对哈希表Hash maps替代方案利用哈希表实现 O(1) 查询重复值处理Handling duplicates必须跳过重复值避免结果中出现重复三元组。本仓库中该题目标注为「三数之和」系列的核心题在 README.md 的完成度表中可看到其 14 种语言的实现状态C、C、C#、Dart、Go、Java、JavaScript、Kotlin、Python、Ruby、Rust、Scala、Swift、TypeScript 均已实现是仓库内覆盖语言最全的题目之一非常适合对照学习不同语言的写法差异。1. 暴力枚举法Brute Force思路暴力法就是穷举所有可能的三元组组合。由于对每个(i, j, k)满足i j k都会检查一次因此一定能找出所有和为 0 的三元组。先排序可以让三元组内部保持升序再借助集合Set天然去重的特性过滤重复结果。算法步骤对数组排序便于处理重复值创建空集合res存放唯一三元组三重循环嵌套枚举外层遍历i中层遍历j i内层遍历k j若nums[i] nums[j] nums[k] 0将排序后的三元组加入集合将集合中的元组转换回列表的列表返回结果。以 Python 实现为例完整多语言版本见原文档以下为 Python 核心class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: res set() nums.sort() for i in range(len(nums)): for j in range(i 1, len(nums)): for k in range(j 1, len(nums)): if nums[i] nums[j] nums[k] 0: tmp [nums[i], nums[j], nums[k]] res.add(tuple(tmp)) return [list(i) for i in res]其他语言实现要点Java / Kotlin用HashSetListInteger/HashSetListInt去重C用setvectorint去重最后转回vectorvectorintJavaScript用Set存JSON.stringify后的字符串最后JSON.parse还原Go用map[[3]int]struct{}作为集合Go 数组可比较天然适合做 map 键Swift / Rust分别用Set[Int]与HashSetVeci32。复杂度分析时间复杂度O(n³)三重循环空间复杂度O(m)外加排序算法占用的空间该复杂度不含输出列表本身O(m)用于在集合中存储唯一三元组最坏情况下m为O(n²)若计入输出列表空间仍为O(m)另加排序空间。其中m为唯一三元组的数量n为给定数组长度。暴力法代码直观、不易出错但 O(n³) 在n较大时完全不可行仅适合作为推导更优解法的起点。2. 哈希表法Hash Map思路排序之后可以固定两个数再用哈希表查找能凑成三元组的第三个数。哈希表count记录每个数字出现的次数当选定第一个、第二个数后临时将其计数减一避免重复使用自身然后检查所需第三个数target -(nums[i] nums[j])在表中是否仍有正计数。排序同时让跳过重复值变得容易保证只输出唯一三元组。算法步骤排序数组组织重复值并便于跳过构建所有数字的频次表count初始化空列表res遍历每个下标i将nums[i]的计数减一防止被复用跳过第一个元素的重复值遍历每个下标j i将nums[j]的计数减一跳过第二个元素的重复值计算所需第三个数target -(nums[i] nums[j])若target计数仍为正则加入三元组内层循环结束后把减掉的计数加回来供下一轮i使用返回res。Python 核心实现完整多语言版本见原文档class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: nums.sort() count defaultdict(int) for num in nums: count[num] 1 res [] for i in range(len(nums)): count[nums[i]] - 1 if i and nums[i] nums[i - 1]: continue for j in range(i 1, len(nums)): count[nums[j]] - 1 if j - 1 i and nums[j] nums[j - 1]: continue target -(nums[i] nums[j]) if count[target] 0: res.append([nums[i], nums[j], target]) for j in range(i 1, len(nums)): count[nums[j]] 1 return res实现细节提醒去重条件j - 1 iJava/C/Go 等写作j i 1保证至少跳过一个元素后才检查重复避免误伤j i 1与i相邻的合法起点每轮i结束后必须恢复计数否则后续轮次频次表被污染最终结果直接追加三元组无需集合去重——排序 频次控制已保证唯一性。复杂度分析时间复杂度O(n²)空间复杂度O(n)不含输出列表O(n)用于频次表若计入输出空间为O(n m)最坏为O(n²)。其中m为唯一三元组数量n为数组长度。哈希表法将暴力法的 O(n³) 降为 O(n²)但引入了 O(n) 的额外空间且计数增删逻辑需要小心维护是面试中值得展示的中间方案。3. 双指针法Two Pointers——最优解思路排序之后固定一个数剩余两个数用双指针查找。排序带来两个好处重复值可以轻易跳过左指针右移会让和增大、右指针左移会让和减小方向完全可预测。对每个固定数a nums[i]放置两个指针l从i 1开始r从数组末尾开始。当前和过大则r左移减小和当前和过小则l右移增大和当和恰好为 0 时记录三元组并跳过两侧重复值。算法步骤排序数组用下标i遍历令a nums[i]若a 0直接break排序后剩余数全为正不可能凑出 0跳过第一个数的重复值i 0 a nums[i-1]设置双指针l i 1r len(nums) - 1当l r时循环计算threeSum a nums[l] nums[r]threeSum 0r左移threeSum 0l右移threeSum 0记录三元组l、r同时内移跳过左指针处的重复值while nums[l] nums[l - 1] and l r返回结果列表。Python 实现python/0015-3sum.py 即为此方案class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: res [] nums.sort() for i, a in enumerate(nums): if a 0: break if i 0 and a nums[i - 1]: continue l, r i 1, len(nums) - 1 while l r: threeSum a nums[l] nums[r] if threeSum 0: r - 1 elif threeSum 0: l 1 else: res.append([a, nums[l], nums[r]]) l 1 r - 1 while nums[l] nums[l - 1] and l r: l 1 return res仓库源码中的边界处理对比对比不同语言实现可以发现几个值得注意的工程细节C 实现c/0015-3sum.c在找到合法三元组后同时跳过左右两侧的重复值nums[left] nums[left - 1]与nums[right] nums[right 1]并使用动态扩容的realloc管理结果数组——这是 C 语言缺少容器库时的典型做法C 实现cpp/0015-3sum.cpp额外在开头增加了if (n 3) return result;的防御性判断并对左右指针的重复值都做了跳过处理Go 实现go/0015-3sum.go在找到三元组后通过nums[num3Idx] nums[num3Idx1]和nums[num2Idx] nums[num2Idx-1]双向去重注释明确标注了「Skip all duplicates from left / right」TypeScript 实现typescript/0015-3sum.ts去重策略最精简仅跳过左指针重复值与 Python 版本一致。这些差异说明双指针去重只需保证不产生重复三元组即可跳左、跳右、或两侧都跳都是正确写法关键是逻辑自洽。复杂度分析时间复杂度O(n²)外层循环 O(n)内层双指针扫描 O(n)总计 O(n²)空间复杂度O(1)不含输出与排序空间若计入输出列表空间为O(m)最坏为O(n²)。其中m为唯一三元组数量n为数组长度。双指针法是本题的标准最优解时间上与哈希表法同为 O(n²)但额外空间只有 O(1)且代码更简洁、去重逻辑更直观是面试与竞赛中的首选方案。常见易错点Common Pitfalls1. 忘记跳过重复值最常见的错误是没有正确处理重复值导致结果中出现重复三元组。排序后无论在外层循环第一个元素还是左指针处找到合法三元组都必须跳过所有相同取值。例如输入[-1, -1, 0, 1, 1]若不去重会得到两个[-1, 0, 1]。2. 忘记先排序双指针法的正确性完全依赖有序数组。不排序时依据和的大小移动指针并不能保证找到所有合法三元组——指针移动方向与元素大小关系无法对应。任何双指针解法前都必须先排序。3. 提前终止条件写错排序后当nums[i]为正时其右侧所有元素也都为正不可能凑出和为 0 的三元组可以安全 break。但break 条件必须是nums[i] 0而不是nums[i] 0若写成 0会漏掉[0, 0, 0]这类以 0 开头的合法三元组。仓库中 c/0015-3sum.c 与 cpp/0015-3sum.cpp 的注释「The array is sorted, there is no possible triplet when this happen」都明确印证了这一剪枝逻辑。三方案对比与选型建议方案时间复杂度空间复杂度核心技巧适用场景暴力枚举O(n³)O(m)含排序空间三重循环 集合去重理解问题、验证正确性哈希表O(n²)O(n)频次计数 临时扣减需要展示哈希思想时双指针O(n²)O(1)排序 指针收缩面试与竞赛首选在nums长度较大如 10⁴ 量级时O(n³) 的暴力法会超时O(n²) 的两个方案均可接受若对额外空间敏感如嵌入式或内存受限环境双指针法因 O(1) 空间而占优——c/0015-3sum.c 的实现正是这种取舍的体现。总结三数之和是「两数之和 → 三数之和 → 四数之和4sum.md」系列问题的核心枢纽暴力法建立正确性基线哈希表法把查找从 O(n) 降为 O(1)双指针法则在 O(n²) 时间内用 O(1) 空间完成求解。掌握本题的排序去重、指针收缩与边界剪枝nums[i] 0而非 0三要素后可以平滑迁移到 three-integer-sum-ii两数之和 II、四数之和等变体题目。建议对照本仓库 14 种语言实现java/0015-3sum.java、javascript/0015-3sum.js、rust/0015-3sum.rs 等逐行阅读体会不同语言在容器选择与边界处理上的差异这对提升多语言刷题能力尤为有效。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 3Sum（三数之和）题解全析：暴力枚举、哈希表与双指针三方案对比
LeetCode 3Sum三数之和题解全析暴力枚举、哈希表与双指针三方案对比【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 15「三数之和」3Sum问题展开完整讲解从暴力枚举到哈希表、再到最优双指针的三种解法覆盖排序去重、指针收缩与频次计数等核心技巧。文章以 articles/three-integer-sum.md 为骨架结合本仓库在 C、C、Go、Java、Python、TypeScript 等 14 种语言中的真实实现见 c/0015-3sum.c、cpp/0015-3sum.cpp、python/0015-3sum.py 等进行源码级印证。读完本文你将掌握三类解法的推导逻辑、去重边界条件、复杂度差异以及面试与刷题中最高频的易错点。问题定义与前置知识问题描述给定一个整数数组nums返回所有和为0且不重复的三元组[nums[i], nums[j], nums[k]]要求i j k。例如输入nums [-1, 0, 1, 2, -1, -4]合法输出为[[-1, -1, 2], [-1, 0, 1]][-1, 0, 1]与[0, 1, -1]视为同一个三元组不能重复输出。动手之前原文档要求你至少熟悉以下四项基础能力排序Sorting对数组排序是高效去重与双指针技术的前提双指针Two pointers最优解法依赖双指针在有序数组中寻找满足目标和的数对哈希表Hash maps替代方案利用哈希表实现 O(1) 查询重复值处理Handling duplicates必须跳过重复值避免结果中出现重复三元组。本仓库中该题目标注为「三数之和」系列的核心题在 README.md 的完成度表中可看到其 14 种语言的实现状态C、C、C#、Dart、Go、Java、JavaScript、Kotlin、Python、Ruby、Rust、Scala、Swift、TypeScript 均已实现是仓库内覆盖语言最全的题目之一非常适合对照学习不同语言的写法差异。1. 暴力枚举法Brute Force思路暴力法就是穷举所有可能的三元组组合。由于对每个(i, j, k)满足i j k都会检查一次因此一定能找出所有和为 0 的三元组。先排序可以让三元组内部保持升序再借助集合Set天然去重的特性过滤重复结果。算法步骤对数组排序便于处理重复值创建空集合res存放唯一三元组三重循环嵌套枚举外层遍历i中层遍历j i内层遍历k j若nums[i] nums[j] nums[k] 0将排序后的三元组加入集合将集合中的元组转换回列表的列表返回结果。以 Python 实现为例完整多语言版本见原文档以下为 Python 核心class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: res set() nums.sort() for i in range(len(nums)): for j in range(i 1, len(nums)): for k in range(j 1, len(nums)): if nums[i] nums[j] nums[k] 0: tmp [nums[i], nums[j], nums[k]] res.add(tuple(tmp)) return [list(i) for i in res]其他语言实现要点Java / Kotlin用HashSetListInteger/HashSetListInt去重C用setvectorint去重最后转回vectorvectorintJavaScript用Set存JSON.stringify后的字符串最后JSON.parse还原Go用map[[3]int]struct{}作为集合Go 数组可比较天然适合做 map 键Swift / Rust分别用Set[Int]与HashSetVeci32。复杂度分析时间复杂度O(n³)三重循环空间复杂度O(m)外加排序算法占用的空间该复杂度不含输出列表本身O(m)用于在集合中存储唯一三元组最坏情况下m为O(n²)若计入输出列表空间仍为O(m)另加排序空间。其中m为唯一三元组的数量n为给定数组长度。暴力法代码直观、不易出错但 O(n³) 在n较大时完全不可行仅适合作为推导更优解法的起点。2. 哈希表法Hash Map思路排序之后可以固定两个数再用哈希表查找能凑成三元组的第三个数。哈希表count记录每个数字出现的次数当选定第一个、第二个数后临时将其计数减一避免重复使用自身然后检查所需第三个数target -(nums[i] nums[j])在表中是否仍有正计数。排序同时让跳过重复值变得容易保证只输出唯一三元组。算法步骤排序数组组织重复值并便于跳过构建所有数字的频次表count初始化空列表res遍历每个下标i将nums[i]的计数减一防止被复用跳过第一个元素的重复值遍历每个下标j i将nums[j]的计数减一跳过第二个元素的重复值计算所需第三个数target -(nums[i] nums[j])若target计数仍为正则加入三元组内层循环结束后把减掉的计数加回来供下一轮i使用返回res。Python 核心实现完整多语言版本见原文档class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: nums.sort() count defaultdict(int) for num in nums: count[num] 1 res [] for i in range(len(nums)): count[nums[i]] - 1 if i and nums[i] nums[i - 1]: continue for j in range(i 1, len(nums)): count[nums[j]] - 1 if j - 1 i and nums[j] nums[j - 1]: continue target -(nums[i] nums[j]) if count[target] 0: res.append([nums[i], nums[j], target]) for j in range(i 1, len(nums)): count[nums[j]] 1 return res实现细节提醒去重条件j - 1 iJava/C/Go 等写作j i 1保证至少跳过一个元素后才检查重复避免误伤j i 1与i相邻的合法起点每轮i结束后必须恢复计数否则后续轮次频次表被污染最终结果直接追加三元组无需集合去重——排序 频次控制已保证唯一性。复杂度分析时间复杂度O(n²)空间复杂度O(n)不含输出列表O(n)用于频次表若计入输出空间为O(n m)最坏为O(n²)。其中m为唯一三元组数量n为数组长度。哈希表法将暴力法的 O(n³) 降为 O(n²)但引入了 O(n) 的额外空间且计数增删逻辑需要小心维护是面试中值得展示的中间方案。3. 双指针法Two Pointers——最优解思路排序之后固定一个数剩余两个数用双指针查找。排序带来两个好处重复值可以轻易跳过左指针右移会让和增大、右指针左移会让和减小方向完全可预测。对每个固定数a nums[i]放置两个指针l从i 1开始r从数组末尾开始。当前和过大则r左移减小和当前和过小则l右移增大和当和恰好为 0 时记录三元组并跳过两侧重复值。算法步骤排序数组用下标i遍历令a nums[i]若a 0直接break排序后剩余数全为正不可能凑出 0跳过第一个数的重复值i 0 a nums[i-1]设置双指针l i 1r len(nums) - 1当l r时循环计算threeSum a nums[l] nums[r]threeSum 0r左移threeSum 0l右移threeSum 0记录三元组l、r同时内移跳过左指针处的重复值while nums[l] nums[l - 1] and l r返回结果列表。Python 实现python/0015-3sum.py 即为此方案class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: res [] nums.sort() for i, a in enumerate(nums): if a 0: break if i 0 and a nums[i - 1]: continue l, r i 1, len(nums) - 1 while l r: threeSum a nums[l] nums[r] if threeSum 0: r - 1 elif threeSum 0: l 1 else: res.append([a, nums[l], nums[r]]) l 1 r - 1 while nums[l] nums[l - 1] and l r: l 1 return res仓库源码中的边界处理对比对比不同语言实现可以发现几个值得注意的工程细节C 实现c/0015-3sum.c在找到合法三元组后同时跳过左右两侧的重复值nums[left] nums[left - 1]与nums[right] nums[right 1]并使用动态扩容的realloc管理结果数组——这是 C 语言缺少容器库时的典型做法C 实现cpp/0015-3sum.cpp额外在开头增加了if (n 3) return result;的防御性判断并对左右指针的重复值都做了跳过处理Go 实现go/0015-3sum.go在找到三元组后通过nums[num3Idx] nums[num3Idx1]和nums[num2Idx] nums[num2Idx-1]双向去重注释明确标注了「Skip all duplicates from left / right」TypeScript 实现typescript/0015-3sum.ts去重策略最精简仅跳过左指针重复值与 Python 版本一致。这些差异说明双指针去重只需保证不产生重复三元组即可跳左、跳右、或两侧都跳都是正确写法关键是逻辑自洽。复杂度分析时间复杂度O(n²)外层循环 O(n)内层双指针扫描 O(n)总计 O(n²)空间复杂度O(1)不含输出与排序空间若计入输出列表空间为O(m)最坏为O(n²)。其中m为唯一三元组数量n为数组长度。双指针法是本题的标准最优解时间上与哈希表法同为 O(n²)但额外空间只有 O(1)且代码更简洁、去重逻辑更直观是面试与竞赛中的首选方案。常见易错点Common Pitfalls1. 忘记跳过重复值最常见的错误是没有正确处理重复值导致结果中出现重复三元组。排序后无论在外层循环第一个元素还是左指针处找到合法三元组都必须跳过所有相同取值。例如输入[-1, -1, 0, 1, 1]若不去重会得到两个[-1, 0, 1]。2. 忘记先排序双指针法的正确性完全依赖有序数组。不排序时依据和的大小移动指针并不能保证找到所有合法三元组——指针移动方向与元素大小关系无法对应。任何双指针解法前都必须先排序。3. 提前终止条件写错排序后当nums[i]为正时其右侧所有元素也都为正不可能凑出和为 0 的三元组可以安全 break。但break 条件必须是nums[i] 0而不是nums[i] 0若写成 0会漏掉[0, 0, 0]这类以 0 开头的合法三元组。仓库中 c/0015-3sum.c 与 cpp/0015-3sum.cpp 的注释「The array is sorted, there is no possible triplet when this happen」都明确印证了这一剪枝逻辑。三方案对比与选型建议方案时间复杂度空间复杂度核心技巧适用场景暴力枚举O(n³)O(m)含排序空间三重循环 集合去重理解问题、验证正确性哈希表O(n²)O(n)频次计数 临时扣减需要展示哈希思想时双指针O(n²)O(1)排序 指针收缩面试与竞赛首选在nums长度较大如 10⁴ 量级时O(n³) 的暴力法会超时O(n²) 的两个方案均可接受若对额外空间敏感如嵌入式或内存受限环境双指针法因 O(1) 空间而占优——c/0015-3sum.c 的实现正是这种取舍的体现。总结三数之和是「两数之和 → 三数之和 → 四数之和4sum.md」系列问题的核心枢纽暴力法建立正确性基线哈希表法把查找从 O(n) 降为 O(1)双指针法则在 O(n²) 时间内用 O(1) 空间完成求解。掌握本题的排序去重、指针收缩与边界剪枝nums[i] 0而非 0三要素后可以平滑迁移到 three-integer-sum-ii两数之和 II、四数之和等变体题目。建议对照本仓库 14 种语言实现java/0015-3sum.java、javascript/0015-3sum.js、rust/0015-3sum.rs 等逐行阅读体会不同语言在容器选择与边界处理上的差异这对提升多语言刷题能力尤为有效。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考