刷穿LeetCode Hot 100：Day 1从哈希表与双指针开始

时间紧基础也就那样想冲一冲校招和社招的算法面试最靠谱的试卷其实就是LeetCode Hot 100。我的Day 1计划很简单把哈希、双指针这两类最基础的题型吃透而不是急着刷数量。身边不少朋友刷了几百题还是心里没底问题多半出在复习没有主线——Hot 100正好提供了这么一条主线哈希负责把“查找”变快双指针负责把“暴力”变省。这篇文章不打算写那种“Day 1打卡”的流水账而是把我这一天的完整思路记下来为什么第一天押这两类题、哈希表到底怎么用才算用对、双指针两种范式怎么区分、做题过程中真实踩过的坑是怎么被排查掉的。适合两类人看一是准备校招/社招算法面试、时间不足三个月的二是刷了不少题但感觉没记住、想重新搭框架的。1. 把Day 1押在哈希和双指针上是最稳的刷题策略1.1 为什么Hot 100被当作面试题的“公因数”Hot 100在算法面试里的地位类似手机上的系统预装应用你未必天天打开但关键时候离不开它。它的题不是按难度排的而是按“面试中出现频率”筛出来的所以很多题你会觉得眼熟两数之和、三数之和、无重复字符的最长子串、盛最多水的容器基本都在里面。有一个数据可以参考我对身边进大厂的同学做过小范围统计算法面里大约七成题目要么和Hot 100重合要么是Hot 100中某道题的变体。这意味着时间不够时把Hot 100刷透比随机刷乱序题库效率高得多。但刷Hot 100有个容易踩的坑很多人按题目编号从1刷到100第一题两数之和做出来了第二题两数相加也还行到第三题无重复字符的最长子串就不是那个味了。因为Hot 100的编排并不是知识专题式而是混合排列顺着刷容易学一个忘一个。所以我的策略是先按“数据结构算法范式”分类先把最基础、出现率最高的哈希和双指针打穿再向外扩展。1.2 哈希和双指针刚好互补能覆盖大量题型的“元模型”说哈希和双指针互补是因为它们在解决同一件事上走了两条完全相反的路哈希牺牲空间换时间用额外存储让查找变快双指针牺牲一定的时间复杂度优化常数、甚至降阶但基本不占额外空间。比如同样是处理“找两个元素满足某种关系”的题哈希的思路是“先存起来再查询”双指针的思路是“排序之后一左一右夹逼”。前者适合无序情况后者适合有序或可以排序的情况。这两个思路相互补充覆盖了两数之和、三数之和、盛水容器、字母异位词分组、最长连续序列、和为K的子数组等一系列Hot 100高频题。在刷题计划里把它们放在同一天还有个好处能形成一个“看题先归类”的习惯。看到题目先判断它属于“查找优化型”还是“遍历优化型”前者往哈希想后者往双指针想。这个判断习惯一旦建立后面刷链表、数组、字符串类题目都会受益。2. 哈希表看似平淡实际上是很多题的第一道突破口2.1 哈希表干了三件事去重、计数、建索引哈希表的底层不复杂就是数组加哈希函数把任意键映射到一个槽位理想情况存取都是O(1)。Python里的dict和set、C里的unordered_map和unordered_set底层就是哈希表它们平均O(1)但最坏情况因为哈希冲突会退化到O(n)。面试考“哈希表怎么实现”的概率不高真正决定你能不能AC的是“什么时候该往哈希上想”。我用了这么多年哈希能解决的无非三类诉求去重用一个Set见到的元素就往里丢已经存在的就说明重复了。典型题是最长连续序列的查重环节以及链表判环时的节点记录。计数用一个Map/字典键是元素值是该元素出现的次数或频次。典型题是“和为K的子数组”中统计前缀和出现的次数。建索引用一个Map记录“值到下标”或“值到位置”典型题就是两数之和遍历一遍边存边查。这里有个习惯值得刻意练习看到题先问自己“我需要知道什么信息这个信息能不能作为键键对应的值是什么”比如字母异位词分组我最初的想法是对每个词排序当键后来发现还可以用26个字母的计数数组当键。键的形式不同解题的维度就不同。顺便说一句哈希树和哈希算法这些热词和刷题里的哈希表不是一回事。哈希树在区块链等领域常被用于快速校验数据但都建立在哈希函数之上刷题阶段用不到哈希树但知道它存在看文章时不至于混淆。另外平时听过“加盐哈希存储”的读者也别急着往这想那是指密码存储时给哈希值加随机盐防撞库和算法题里的哈希表只是同一个基础概念的工程应用。2.2 从两数之和到和为K的子数组识别哈希的变形两数之和是全网最经典的哈希入门题。暴力解法就是双重循环O(n²)用哈希的目标就是把“找target - nums[i]”这一内层循环从O(n)降到O(1)。def twoSum(nums, target): seen {} for i, num in enumerate(nums): if target - num in seen: return [seen[target - num], i] seen[num] i return []注意是边遍历边存而不是先全部存完再查否则同一个元素会被自己“补”成target。这道题的价值不在于代码有多难而在于让你记住哈希的“边存边查”模式。有了这个基础再做“和为K的子数组”就顺多了。题目要求统计连续子数组和等于K的个数。常规思路是固定左端点、移动右端点累加O(n²)优化方向是引入前缀和。令前缀和pre[i]表示从0到i的和那么子数组[j1, i]的和等于pre[i] - pre[j]只要pre[i] - pre[j] K即pre[j] pre[i] - K。于是问题又变成了“找多少个子前缀和等于pre[i] - K”。这正好用哈希计数来做def subarraySum(nums, k): prefix 0 count 0 mp {0: 1} for num in nums: prefix num count mp.get(prefix - k, 0) mp[prefix] mp.get(prefix, 0) 1 return count这一步把O(n²)优化到O(n)而且代码量并不大。关键在于初始化mp[0] 1因为当前缀和本身等于K时要能从0开始计数。这个细节我一开始漏了直接导致样例过不去下面实战部分会细说。2.3 空间换时间不是无脑换哈希也有账要算哈希好用但有个前提你得想清楚空间换时间换来的时间值不值付出的空间扛不扛得住。举例有一类题目数据范围很小比如数值只有0到100那直接用数组当哈希表可能更好甚至更快。因为数组下标访问是天然的O(1)没有哈希函数和冲突的开销。反之如果键是字符串、元组这类复杂对象或者数据范围很大很稀疏才真的需要dict或unordered_map。另一个常见误区是用哈希去存“所有”信息结果空间复杂度被抬高了。比如最长连续序列这题很多人一上来就排序O(n log n)其实题目要求O(n)就只好用哈希。做法是先把所有元素放进Set然后只对“当前元素减1不在Set里”的元素启动向后探测这样每个元素最多被访问两次总复杂度O(n)。这个例子说明哈希不是让你把所有事都扔给额外存储而是用它换一个重新设计遍历流程的机会。空间换时间要算账换来的时间复杂度降低是否关键付出的空间是否在可接受范围这两个问题想清楚哈希才算用对。3. 双指针一快一慢、一左一右两类范式要分清楚3.1 相向双指针左右往中间走先把暴力降一个数量级相向双指针的典型场景是排序数组上的查找问题左右两个指针分别指向数组两端根据当前两个指针指向元素的关系决定移动左还是右。以三数之和为例暴力解法是三层循环O(n³)用排序加双指针优化到O(n²)固定第一个数剩下的区间用左右指针夹逼。关键点有三个一是有序性必须先把数组排序二是去重固定数和左右指针移动时都要跳过重复值否则结果里全是重复三元组三是移动规则两数之和大于目标时右指针左移小于目标时左指针右移等于时就记录并同时收缩两边。相向双指针另一个容易考的是“盛最多水的容器”它的移动规则和“和”无关而是谁矮移动谁。很多人死记这个结论过一阵又忘了。我当时理解透了才记住容器的面积是两边较短的那根决定高度所以只有移动较矮的那一端面积才有变大的可能如果移动高的那端高度不变或变矮宽度还在缩小面积只会更小。这个“移动收益”分析比背规则可靠。3.2 同向双指针滑动窗口的收缩时机是灵魂同向双指针又称滑动窗口两个指针都从左往右移动右指针负责扩展窗口左指针负责收缩窗口。它的经典使用场景是“连续子数组/子串满足某个条件”。无重复字符的最长子串是很好的入门题def lengthOfLongestSubstring(s): seen set() left 0 ans 0 for right, ch in enumerate(s): while ch in seen: seen.remove(s[left]) left 1 seen.add(ch) ans max(ans, right - left 1) return ans这里每个字符最多进出窗口一次总复杂度从暴力O(n²)降到O(n)。滑动窗口最难理解的一点是为什么右指针不用回溯因为窗口只会在一个方向移动左指针走过的字符已经不可能再对当前最优解有贡献。大多数人在这一步会卡住我的建议是画图把指针位置和Set内容画出来连续推演几个例子比看十遍讲解都有用。3.3 边界条件反复错移动规则用“写死”代替“感觉”双指针的代码往往很短但错起来很隐蔽我统计过多次出错的高频点几乎全在边界退出条件写错相向双指针用left right还是left right取决于你是否要处理“左右指针指向同一元素”的情况。两数之和类题用left right因为同一元素不能重复使用回文判断也常写成left right避免中间字符被重复比较。指针移动时机不对记录答案之后再移动指针还是移动之后才记录结果完全不同。我见过不少人把“相等时记录并同时收缩”写成了“先移动再判断”导致漏解。窗口内状态没同步更新滑动窗口的Set或计数Map必须在指针移动时同步增删少了这一步窗口统计就是错的而且很难通过样例发现。我给自己的硬性要求是双指针题先写下移动规则的“纯文字版”。比如“当和小于targetleft加1当和大于targetright减1当两者相等记录并同时收缩”再翻译成代码。把规则写死写代码的时候就不会靠感觉瞎动。3.4 一道题看清指针移动条件盛最多水的容器盛最多水的容器非常适合验证上面说的“移动收益”分析。题目给一个高度数组要求选出两根柱子使它们和x轴围成的容器能装最多水。水的体积 min(height[left], height[right]) × (right - left)。如果移动较高的指针min高度不会增加可能变小宽度一定变小所以面积必然不增而移动较矮的指针虽然宽度变小但min高度有可能变大所以面积有增大的机会。所以要找最大面积每次都应该移动较矮的一端。这道题让我明白双指针的核心不是“左右挪一挪”这种表面操作而是每一步都在消除“不可能成为最优解”的候选者。能证明某部分候选永远不可能是最优指针就可以安全地越过它。理解了这一层很多双指针题包括接雨水都能想得通。4. Day 1的实战记录从读题到AC的完整链路4.1 我的做题顺序审题10分钟思考15分钟动手30分钟很多刷题新手败在“看题5分钟写代码1小时最后没AC还背答案”。我Day 1给自己定的节奏是这样的阶段时间核心目标审题10分钟搞清输入、输出、约束尤其是数据范围思考15分钟先想暴力解再想暴力慢在哪最后设计优化动手30分钟把优化思路写成代码跑测试用例审题阶段只做一件事把题目的输入、输出、约束条件全部看明白尤其是数据范围。比如n最大10^5说明O(n²)大概率超时这时就去想O(n)或O(n log n)如果看到“字符串只包含小写字母”那数组哈希可能比字典更快因为可以直接开一个26长度的计数数组。思考阶段我会在纸上画样例试着用最暴力的方法解一遍再想“暴力慢在哪一步”。慢在查找就试哈希慢在重复遍历就试双指针或滑动窗口。这个“从暴力到优化”的推导链条比直接记住最优解重要得多因为面试官真正想听的也是这个推导过程。动手阶段才是写代码。我要求自己每写一个关键步骤都能说出理由而不是默写模板。比如写哈希表存下标的行我会在想存这行是为了让后面的查询变成O(1)而不是单纯因为“这道题要用哈希”。4.2 一次真实翻车暴力解法TLE之后的排查链路Day 1里最值得记录的不是顺利AC的题而是一次真实翻车。我在做“和为K的子数组”的时候第一反应是滑动窗口写着写着发现不对劲——滑动窗口通常要求窗口内满足单调性即数组全为正数才能保证窗口越大和越大。但这道题数组里有负数窗口收缩后和可能变大也可能变小滑动窗口的单调性假设被破坏直接用它会有漏解。我当时的第一版实现是用暴力固定左端点枚举右端点小型数据能过提交后TLE一看数据范围是10^4左右O(n²)的运算量在超时边缘。排查链路是这样的先确认复杂度算10^4的平方是10^8大概率超时问题不是代码小细节而是算法复杂度不达标。再确认滑动窗口是否可用有负数前缀和不是单调的不能用同向双指针。转向前缀和加哈希计数把问题转成“统计pre[j] pre[i] - K出现的次数”。实现时注意初始化mp[0] 1因为前缀和本身等于K的情况要从0开始计数。这个翻车经历让我记住了一个非常重要的区分滑动窗口只适用于单调性成立的问题遇到负数或条件不具备单调性就别硬套换哈希前缀和反而更通用。4.3 错题本应该记什么才能让第二遍更高效Day 1结束之后我花了二十分钟整理错题本。和大多数人把代码抄一遍不同我只记四样东西这题的标签比如“哈希-前缀和”、“双指针-相向”。暴力方法为什么慢比如“双重循环找两个数内层查找O(n)”。优化思路的一句话比如“空间换时间用哈希表把内层O(n)查询变成O(1)”。最关键的边界条件比如“和为K的子数组mp[0]要初始化为1”。这样做的好处是第二遍复习时我不需要重新读一遍题目和代码而是直接看标签和优化思路在脑子里把解法过一遍。过不出来的才值得重新做。这个方法看起来简单但真的帮我节省了大量二刷时间我从“题做了几百道”变成了“题会了大几百道”。5. 第一天的复盘清单与后续安排5.1 复盘时问自己三个问题当天刷完一计算我发现真正有效的不是刷了多少题而是复盘。复盘时候只问自己三个问题第一我今天遇到的题分别属于哪一类能不能用一句话说出识别特征比如“要求连续子数组满足某个条件且数组没有负数优先想滑动窗口”“无序找两数关系优先想哈希”。第二有没有哪道题我是背了答案而不是理解了解法背答案的标准是换一个相近的输入解法就不成立了。如果有回头把推导过程重新走一遍用白纸从暴力推演到优化。第三我今天的代码里有没有“凭感觉写的部分”有就标红贴上原因。比如我把相向双指针的退出条件写错过标红原因就是“没区分left right和left right的语义”。标红记录比单纯抄一遍代码有用十倍。5.2 接下来几天的刷题节奏Day 1结束了但我没打算第二天直接开新专题。我会在Day 2先花二十分钟把Day 1的高频题重新默写一遍特别是两数之和、无重复字符的最长子串、盛最多水的容器这三道因为它们分别代表了哈希、同向双指针、相向双指针的“元模型”。默写对了再进入下一个专题。后续我打算按这样的节奏推进每个专题至少集中练两天第一天跟本专题的经典题第二天刷变体题和混合题。第三天就开始穿插复习旧专题用随机选题来检验是不是真的会了。Hot 100一共100道按这个节奏一个半月能过完一遍再留出半个月做二刷和三刷时间上完全来得及。最后再分享一个个人体会第一天刷题别把目标定成“做出100道中的20道”而应该定成“建立对哈希和双指针的肌肉记忆”。肌肉记忆来自重复推演不来自背答案。我做盛最多水的容器时第一次看完题解觉得懂了第二天合上书重写指针移动条件还是写反。第二遍自己从头把“移动较矮一端才有收益”推导一遍才真正内化。所以Day 1的意义不是进度条前进了几个点而是你是否真的具备了自己推导出解法链条的能力。这个能力有了后面的90多道题才会越刷越顺。