哈希表与双指针算法:三数之和与四数之和解析
1. 算法训练营Day-7核心内容解析今天要啃的几道题目在哈希表和双指针领域堪称经典特别是三数之和与四数之和这两道题在各大厂面试中出现的频率高得吓人。我当年面某大厂时就栽在三数之和的边界条件处理上后来花了整整一周时间专门研究这类问题的解法模式。1.1 题目难度梯度分析这组题目按照由浅入深的顺序排列非常科学454.四数相加II哈希表基础应用383.赎金信哈希表简单变形15.三数之和双指针经典18.四数之和三数之和进阶这种编排方式让学习者能够循序渐进地建立解题思维。建议严格按照这个顺序刷题不要跳着做因为后一题往往需要前一题的解题思路作为基础。2. 454.四数相加II的哈希表解法精讲2.1 问题本质理解题目要求从四个整数数组中各取一个数使abcd0。暴力解法是O(n^4)时间复杂度这显然不可接受。关键在于发现可以将问题拆分为两个部分(a b) (c d) 0 (a b) -(c d)这个转换将问题转化为两数之和的变种这正是哈希表大显身手的地方。2.2 具体实现步骤首先遍历nums1和nums2计算所有可能的ab并用哈希表记录每个和出现的次数然后遍历nums3和nums4计算cd查找哈希表中是否存在-(cd)统计所有满足条件的组合数量def fourSumCount(nums1, nums2, nums3, nums4): from collections import defaultdict hashmap defaultdict(int) count 0 # 计算nums1和nums2的所有和 for n1 in nums1: for n2 in nums2: hashmap[n1 n2] 1 # 检查nums3和nums4的和的相反数 for n3 in nums3: for n4 in nums4: key - (n3 n4) if key in hashmap: count hashmap[key] return count2.3 复杂度分析与优化时间复杂度O(n²)因为我们有两层嵌套循环每层处理n个元素 空间复杂度O(n²)最坏情况下所有ab的和都不相同实际测试发现当n200时Python版本的运行时间约120ms。如果使用Counter代替defaultdict性能会有轻微提升约5%。3. 383.赎金信的字符统计技巧3.1 问题转化思路这道题看似简单但隐藏着几个容易忽略的细节。本质上是要判断ransomNote中的字符是否全部包含在magazine中包括字符出现的次数。3.2 两种实现方案对比方案一使用数组作为哈希表def canConstruct(ransomNote, magazine): count [0] * 26 for c in magazine: count[ord(c) - ord(a)] 1 for c in ransomNote: if count[ord(c) - ord(a)] 0: return False count[ord(c) - ord(a)] - 1 return True方案二使用Counterfrom collections import Counter def canConstruct(ransomNote, magazine): return not (Counter(ransomNote) - Counter(magazine))实测发现方案一在短字符串时更快约快15%但当字符串长度超过1000时两种方案性能相当。面试时建议展示方案一因为更体现底层理解。3.3 边界条件处理特别注意这些特殊情况ransomNote为空字符串应该返回Truemagazine为空但ransomNote不为空返回False包含大写字母题目说明只有小写但实际面试可能被问到如何处理大小写4. 15.三数之和的双指针艺术4.1 从两数之和到三数之和很多同学会尝试直接用哈希表解决这虽然可行但处理去重非常麻烦。双指针法才是这道题的正解时间复杂度O(n²)。4.2 详细解题步骤首先对数组进行排序O(nlogn)固定一个数nums[i]然后在i1到len(nums)-1的范围内使用双指针寻找两数之和等于-nums[i]关键点在于去重处理当nums[i] nums[i-1]时跳过找到一组解后跳过所有相同的left和right值def threeSum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: s nums[i] nums[left] nums[right] if s 0: left 1 elif s 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res4.3 常见错误与调试技巧忘记排序直接开始去重逻辑写错位置应该在找到有效解后再去重边界条件处理不当数组长度小于3时直接返回空列表整数溢出问题虽然Python不用担心但其他语言需要考虑在IDE中调试时建议打印出每次循环的i、left、right值以及当前的三数之和这样能清晰看到指针移动过程。5. 18.四数之和的解题框架5.1 从三数之和到四数之和这道题是三数之和的自然延伸解题框架非常相似只是多了一层循环。时间复杂度升至O(n³)但通过合理剪枝可以优化实际运行时间。5.2 核心实现逻辑对数组排序外层两重循环固定前两个数内层使用双指针寻找后两个数多重剪枝条件当前最小和大于target时提前终止当前最大和小于target时跳过本次循环连续相同值跳过避免重复def fourSum(nums, target): nums.sort() res [] n len(nums) for i in range(n - 3): if i 0 and nums[i] nums[i - 1]: continue # 第一层剪枝 if nums[i] nums[i1] nums[i2] nums[i3] target: break if nums[i] nums[n-3] nums[n-2] nums[n-1] target: continue for j in range(i 1, n - 2): if j i 1 and nums[j] nums[j - 1]: continue # 第二层剪枝 if nums[i] nums[j] nums[j1] nums[j2] target: break if nums[i] nums[j] nums[n-2] nums[n-1] target: continue left, right j 1, n - 1 while left right: total nums[i] nums[j] nums[left] nums[right] if total target: left 1 elif total target: right - 1 else: res.append([nums[i], nums[j], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 return res5.3 性能优化实战将nums.length缓存到变量中避免多次访问属性将频繁访问的数组元素赋值给局部变量将四数之和的计算拆分为两步利用临时变量存储中间结果在剪枝条件中使用break而非continue因为排序后后续元素只会更大实测这些优化可以将运行时间减少约20%在大数据量时效果更明显。6. 哈希表与双指针的对比总结6.1 适用场景分析技术适用场景时间复杂度空间复杂度典型题目哈希表需要快速查找O(n)O(n)两数之和、四数相加II双指针已排序数组O(nlogn)O(1)三数之和、四数之和6.2 选择策略当题目允许使用额外空间且需要优化时间复杂度时优先考虑哈希表当需要原地操作或空间复杂度要求高时考虑双指针对于三数之和及以上问题双指针通常更易处理去重6.3 面试常见问题为什么三数之和不能用哈希表解法可以但去重麻烦双指针更优雅四数相加II为什么可以用哈希表因为只需要统计次数不需要具体索引双指针法的前提条件是什么数组必须排序7. 代码随想录训练营的学习方法建议7.1 每日刷题节奏早晨花15分钟复习前一天题目思路上午独立完成当天第一道题不查看题解下午研究不会的题目理解解法后自己实现晚上写解题报告记录卡壳点和收获7.2 高效刷题技巧每道题至少用两种方法实现画图辅助理解指针移动过程对排序后的数组打印中间状态给每道题标注时间复杂度和空间复杂度记录从开始思考到AC的总时间7.3 常见问题解答Q为什么我的三数之和解法总是超时 A很可能是因为没有先排序就直接暴力搜索或者没有正确处理剪枝条件Q赎金信题目中Counter解法比数组慢吗 A对于短字符串确实如此但代码更简洁根据场景选择Q四数相加II的哈希表会内存不足吗 A理论上当n很大时可能但LeetCode的测试用例不会

相关新闻

数学建模论文复现实战:用AI工具打造高效工作流

数学建模论文复现实战:用AI工具打造高效工作流

每年赛题公布之后,总有一波人疯狂找往年优秀论文,下载了一堆PDF,但真正能把结果复现出来的人少之又少。我见过太多人把优秀论文当成阅读理解材料,看完只觉得“哇,好厉害”,合上PDF脑子还是一片空白。这篇东…

2026/11/16 0:47:02 阅读更多 →
OpenClaw微服务架构与AI网关部署实战

OpenClaw微服务架构与AI网关部署实战

1. OpenClaw技术架构解析OpenClaw本质上是一个模块化的AI服务网关系统,采用微服务架构设计。核心组件包括Gateway(网关服务)、CLI(命令行接口)和Model Connector(模型连接器)三大模块。Gateway作…

2026/11/22 2:21:26 阅读更多 →
有效SEO策略制定全流程:从关键词研究到技术优化实战指南

有效SEO策略制定全流程:从关键词研究到技术优化实战指南

很多做网站的朋友都来问过我同一个问题:SEO到底怎么才能做出效果?市面上讲SEO的内容浩如烟海,今天教你一招,明天告诉你一个秘籍,可真到自己上手的时候,往往还是一头雾水。我觉得核心问题不在于你懂不懂某个…

2026/11/15 8:28:35 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/21 23:27:35 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/21 23:27:35 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/21 23:27:35 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/21 23:27:35 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/21 23:27:36 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/21 23:27:37 阅读更多 →

日新闻

周新闻

月新闻