LeetCode Hot 100刷题第一天：从哈希表与双指针开始-北京尧图网络

1. 为什么第一天从哈希和双指针开始很多人刷LeetCode Hot 100时容易陷入一个误区就是按照题号从前往后刷或者每天按难度挑几道这样刷完就忘两周后回头看跟没刷一样。我自己把Hot 100刷了三轮之后最大的感触是如果让我重新安排刷题顺序第一天一定会先集中打穿哈希和双指针这两类题。原因很简单。Hot 100里哈希和双指针的题目加起来接近三十道占比接近三分之一而且这两类题恰好是面试中最常被问到的“入门天花板”和“进阶地板”。哈希表解决了大量“暴力搜一遍是O(n²)想优化成O(n)”的问题双指针则把很多需要两重循环的问题降成一重或线性的遍历。它们本质上就是你在算法题里最先接触到的两种优化思维空间换时间、利用有序性省去无效遍历。不管你是刚准备校招的在校生还是工作了两三年想跳槽的工程师Day 1从这两块切入收益是最确定的。新手能在两三个小时内看到自己“暴力解法→优化解法”的转变老手也能借这两类题目把基础动作重新打磨一遍。这篇内容我不打算堆概念就按我自己第一天的实际做法来讲重点是每一类题到底怎么识别、怎么下手、有哪些坑。1.1 哈希表空间换时间的第一课哈希表这个东西用过HashMap的人都知道它键值对查询是O(1)但真正做题时很多人想不起来用。它的核心作用其实就是一句话把“查找某个元素是否存在/位置在哪”这个动作从O(n)变成O(1)代价是额外开一个O(n)的存储。这个思路在算法题里太常用了以至于LeetCode Hot 100单独给它划了一类。你做第一题“两数之和”时如果没用哈希表大概率会写两层for循环那当然也能过。但当你走到“字母异位词分组”“最长连续序列”这类题时没有哈希思维就完全无从下手。所以Day 1先花一个晚上把哈希的套路吃透后面刷图论、树的题目很多地方都能复用这层理解。哈希表在工程上还有哈希函数设计、冲突解决、扩容这些复杂话题但刷题阶段你只需要关注两件事存什么和怎么查。存的是键值对键选什么、值存什么决定了整个算法的形态。1.2 双指针把O(n²)压成O(n)的常见套路双指针这个名字听起来有点玄其实就是用一前一后或一快一慢两个指针完成对数组或链表的遍历核心是为了利用某种单调性把原本重复的遍历过程去掉。最常见的三个变体左右夹逼用于有序数组或能推导出单调性的问题、快慢指针用于链表环检测或原地处理、滑动窗口用于子串或子数组问题。举个例子最经典的“盛最多水的容器”和“三数之和”第一反应都是两重循环甚至三重循环。一旦你把左右两个指针放好根据当前结果决定是移动左指针还是右指针复杂度立刻降一个量级。这种“不需要比较每一对组合”的思维正是双指针题目的核心。很多同学刷双指针时最大的困惑是“什么时候应该想到用双指针”而不是“怎么写双指针”。这个我在第三章专门讲先不展开。总之哈希和双指针其实是递进关系哈希解决“查找快”双指针解决“遍历省”Day 1把这两个都过了后面动态规划、图论的很多最优化解法你才能看得懂。1.3 这两类题背后的核心思维模式我刷题刷多了之后发现Hot 100以及绝大多数算法面试题本质上只在考察四件事穷举、缓存、收敛、取舍。穷举是暴力法缓存就是记忆化或哈希收敛就是双指针、二分这类利用单调性快速缩小搜索范围取舍则是贪心和动规。而哈希和双指针恰好是“缓存”和“收敛”这两个思维最纯粹的代表。所以第一天打透它们不只是为了会做那十几道题而是为了在后面遇到完全没见过的题目时能够第一时间从脑子里的“套路库”里调出这两种视角去尝试。这也就是为什么很多刷题经验贴都说“算法题刷到后期拼的是套路识别不是灵光一现”。Day 1的这两类题就是你套路库的第一块地板。2. 哈希表的经典题型与实战拆解哈希表在Hot 100里的题目大致可以分成三种记出现位置、记出现次数、唯一化映射。下面我用三道典型题来拆解这三道题我建议你Day 1必须亲手写一遍它们覆盖了大部分哈希的应用场景。2.1 “两数之和”从暴力到哈希的完整思维转变两数之和几乎是人人都做过的题题目是给定一个整数数组和一个目标值找出数组中和为目标值的两个数的下标。最暴力的做法自然是两层循环每个数都和后面的数加一次时间复杂度O(n²)。这个思路的问题在于内层循环每次都在做一次线性查找而查找这件事本来可以用哈希表优化。正确的思路是遍历数组时把“当前数”和“它的下标”存进哈希表同时检查“目标值减当前数”是否已经在哈希表里。如果存在就直接返回两个下标。这样一来每一轮操作都是O(1)的查找和插入整体复杂度降为O(n)。这里有一个细节很容易被忽略是先查再存还是先存再查答案是先查再存。如果先把当前数存进去了再查目标差值当目标值正好是当前数两倍的时候会把自己也算进去比如target6当前数是3查6-33正好查到刚存的自己返回的下标就会是[i, i]这显然不对。我第一次写的时候就在这个细节上翻了车。def twoSum(nums, target): seen {} for i, num in enumerate(nums): diff target - num if diff in seen: return [seen[diff], i] seen[num] i return []这道题想传递的核心思想其实很简单如果你发现自己在一个循环里反复查找某个值就想想能不能先用哈希表把查找表建好。后面遇到的“和为K的子数组”“两数之和II”等变体都是在这个基础上增加一点条件。2.2 “字母异位词分组”和“最长连续序列”连着刷收获更大这两道题放在一起刷是因为它们恰好展示了哈希表的两种高阶作用作为归类的key以及作为去重快速查找的集合。字母异位词分组的题目是给一组字符串把字母异位词字母重新排列后相同的词分到同一组。最容易想到的思路是把每个字符串排序排序后相同的字符串就是同一组。用哈希表把“排序后的字符串”映射到“原字符串列表”一次遍历就完成了分组。这个解法巧妙在用排序后的结果当作哈希键这是哈希思维里非常经典的“归一化”手法。如果你对Python熟悉写法非常简短def groupAnagrams(strs): groups {} for s in strs: key .join(sorted(s)) groups.setdefault(key, []).append(s) return list(groups.values())最长连续序列稍微难一点给定一个未排序的整数数组找出数字连续的最长序列的长度要求时间复杂度O(n)。这道题如果你第一反应是排序后遍历那就掉进陷阱了排序是O(n log n)题目明确要求O(n)。正确做法是把所有数放进一个哈希集合然后只从连续序列的起点开始数。怎么判断一个数是不是序列起点很简单看这个数减1是否在集合里如果不在说明它是起点然后从它开始一步步往后数。每个数最多被访问两次一次判断、一次计数总复杂度O(n)。这道题用哈希集合的去重和O(1)查询能力完美展现了“空间换时间”的价值。2.3 哈希表使用中的三个细节刷哈希表题目时有几个细节是很多人容易忽略的我单独列出来键的选择要保证唯一性和可还原性。比如字母异位词分组里用排序后的字符串做键就是唯一的归一化结果。如果直接用字符串本身做键那“abc”和“bca”就进不了同一组。反例是有些题适合用字符计数元组做键比如同字符不同数量的情况要根据题目灵活选。遍历字典的同时不要修改字典。在Python里如果边遍历边往字典里添加元素会直接报RuntimeError。如果你需要在原有hash表基础上更新可以先取出keys或者用新字典存储。值存什么要想清楚。两数之和存的是下标字母异位词分组存的是列表有些题还需要存“最后一次出现的下标”或“累计次数”。存错类型后面代码就会很别扭。这三个细节我第一天刷完就记进了笔记后来发现它们出现的频率极高几乎每道哈希题都会触及其中一个。3. 双指针的三种模式与实战拆解双指针的题看着多万变不离其宗。我习惯把Hot 100里的双指针题分成三类左右夹逼、快慢指针、滑动窗口。每一种模式都有适合它的场景和固定的思考路径。下面我挑三道有代表性的题分别拆开讲。3.1 左右夹逼盛最多水的容器与三数之和左右夹逼模式适用于数组有序或者经过排序后可以有序化的场景。核心逻辑是左指针和右指针指向数组两端根据当前状态决定移动哪一边每一步都排除掉一部分不可能的解。先看“盛最多水的容器”题目是给一个数组每个元素代表高度找两个元素和x轴围成的容器能装最多水。暴力的做法是枚举任意两根柱子计算面积O(n²)。双指针的思路是左右指针初始指向数组两端容器高度取决于较矮的那根面积等于“矮高度 × 指针间距”。接下来移动较矮的那一侧指针因为如果移动较高的一侧容器高度只可能不变或变矮而宽度变小面积必然变小只有移动较矮侧才有机会遇到更高的柱子。我第一次刷的时候代码写了十分钟不到但理解“为什么移动矮的那端一定不会错过最优解”反而花了不少时间。这也是很多同学感觉双指针题“代码好写但思路难想”的原因。def maxArea(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans三数之和则是另一类夹逼应用先排序然后固定一个数作为target剩下两个数用左右指针在有序数组里找目标。这个套路后面还会在“四数之和”“最接近的三数之和”里用到属于值得刻在脑子里的模板。3.2 快慢指针链表中环与数组原地操作快慢指针的经典用法有三个判断链表是否有环、找到环的入口、链表找中间节点。Hot 100里“环形链表”和“环形链表II”就是这种题的代表。快指针每次走两步慢指针每次走一步如果链表中存在环两者必然在环内相遇。这个原理其实和操场跑步一样速度不同的人最终会在某一圈相遇。基于这个基础你还能进一步推导出“如果在相遇点后一个从head出发、一个从相遇点出发两者速度一致则它们相遇的地方就是环入口”的结论。这个结论刚看会觉得玄幻但画个图推一遍就明白了它本质上是利用了快指针比慢指针多走的那一段与起点到环入口的距离之间的等量关系。数组上的快慢指针则常用于“移动零”这类题。移动零的要求是把所有0移到数组末尾同时保持非零元素的相对顺序。最直接的方式是维护一个slow指针表示下一个非零元素应该放的位置快指针遍历数组遇到非零就把它放到slow位置上slow加一。遍历结束把slow之后的位置全部填0。整个过程只需要一次遍历O(n)时间O(1)额外空间。def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1这个“双指针原地交换”的思路在“移除元素”“删除排序数组中的重复项”这些题里高度通用本质上就是用快指针负责扫描慢指针负责维护结果数组的边界。3.3 滑动窗口无重复字符的最长子串滑动窗口是双指针概念在全网被讨论最多的变体但我必须说实话滑动窗口和普通双指针的思维模式并不完全一样普通双指针的重点是“移动哪一边”滑动窗口的重点是“维护窗口内状态的合法性”。以“无重复字符的最长子串”为例。暴力做法是枚举所有子串检查每个子串里有没有重复字符O(n²)甚至O(n³)。滑动窗口的思路是右指针不断向右扩展窗口把新字符加进来一旦发现当前窗口内有重复字符左指针就不断右移直到重复字符被移出去为止。窗口的最大长度就是答案。这个过程中最关键的是用一个哈希集合或数组来记录窗口内有哪些字符并且左右指针都只能前进、不能回退。整个算法的时间复杂度是O(n)因为每个字符最多被加入和移除窗口一次。def lengthOfLongestSubstring(s): window set() left 0 ans 0 for right, ch in enumerate(s): while ch in window: window.remove(s[left]) left 1 window.add(ch) ans max(ans, right - left 1) return ans滑动窗口的识别特征也很明显题目要求连续子数组/子串的最长、最短、满足某条件的最值那九成可以往滑动窗口上想。除了这道题“最小覆盖子串”“字符串的排列”“找到字符串中所有字母异位词”都是同一个模板。3.4 双指针题型的通用判定条件很多读者会问到底怎么判断一道题是不是双指针结合我自己的经验给你几个判断标准题目涉及数组或链表上的“区间”或“一对元素”大概率可以往双指针想。暴力解法复杂度是O(n²)并且有明显单调性可利用比如数组排序后、指针向内移动方向与答案单调相关就可以考虑双指针。题目询问“最长子串”“最短子数组”且要求连续优先尝试滑动窗口。链表题要求判断环、找入环点、找中间节点直接上快慢指针。如果一道题你看了五分钟想不出解法可以先自问一句“这个暴力解法里的哪一次比较是可以省掉的”能省掉比较的地方通常就是双指针可以切入的地方。4. Day 1题单与执行节奏Hot 100的题目数量有100道但一天不可能刷完。Day 1的核心目标是建立哈希和双指针的基础识别能力而不是追求题量。我帮你整理了一份我实际验证过的Day 1题单共10道题全部来自Hot 100按顺序刷效果最好。4.1 我建议的10题题单这10道题的选择原则是基础和进阶搭配哈希和双指针交叉出现。每道题我都标注了它考察的核心点。题号题目核心考点建议用时1两数之和哈希表记位置15分钟49字母异位词分组哈希键的归一化15分钟128最长连续序列哈希集合起点判断25分钟283移动零快慢指针原地操作10分钟11盛最多水的容器左右夹逼20分钟15三数之和排序左右夹逼30分钟3无重复字符的最长子串滑动窗口哈希集合25分钟42接雨水左右指针进阶35分钟141环形链表快慢指针10分钟142环形链表II快慢指针推导环入口25分钟总计时大约3.5小时。实际刷的时候肯定会有题目卡壳尤其是接雨水和环形链表II卡壳才是正常的千万别怀疑自己。如果时间只够刷6道建议优先保证两数之和、字母异位词分组、移动零、盛最多水的容器、三数之和、无重复字符的最长子串这6道。4.2 当天怎么安排复习节点我自己的刷题节奏是“先题后理再复述”具体到Day 1执行流程是这样的上午/开始阶段先做题单里的前4道题刻意控制自己在看答案前至少独立思考20分钟。如果完全没思路允许看题解的开头部分只看到“用哈希表”或“用双指针”这个提示级别不要看完整代码。中间阶段刷完4道最基础的题后停下来总结一下三道题各自的套路把“哈希表记什么、双指针移动哪边”写下来。这一步千万别省理解了套路再做后面接雨水这类题思路是自然长出来的而不是背下来的。收尾阶段完成剩余题目后拿出一张空白纸把当天所有题的思路默写一遍重点写“一开始想的暴力解法是什么、优化解法为什么能省时间、边界条件有哪些”。这个复述动作能帮你把短期记忆转成长时记忆很多人刷完就忘就是因为跳过了这一步。有些经验贴会建议用Anki或者Notion做记忆卡片我个人的感觉是形式不重要关键是当天晚上要主动回忆一遍解法而不是仅仅“做过”。4.3 刷题记录模板分享一个我常年用的刷题记录模板结构很简单每道题占一个卡片题目名与编号你最初的思路哪怕很粗糙优化解的思路用一句大白话说明“为什么能优化”代码实现中的关键边界条件是否在20分钟内独立解出是否需要在第二天重刷比如两数之和的记录我会写成最初思路两层for枚举优化思路先查diff在不在哈希表里再存当前元素用空间换时间边界条件注意要先查再存否则会把自己匹配进去独立解出是重刷不需要这个模板最大的价值在于你刷完整个Hot 100之后回看能一眼看出自己的薄弱点在哪些题型上后续集中突破就很有针对性。5. 第一天踩坑记录哈希与双指针的高频翻车点Day 1刷题时有几个错误我几乎在每轮刷题中都会看到新手踩进去我自己第一轮刷的时候也没跑掉。这里集中整理一下希望你能避开这些坑。5.1 哈希表使用中的四个隐藏陷阱第一个坑是用哈希表存了值但没有考虑重复元素。两数之和的变体题里如果数组里有重复的相同数字你在存哈希时用“值→下标”的映射后出现的下标会覆盖前面的。应对办法是提前想好是否需要存储“最后一次出现的下标”还是“第一次出现的下标”或者改用“值→下标列表”。第二个坑是把哈希表当作万能缓存忽视了空间限制。有些题目数组长度非常大你的哈希表也跟着变成O(n)空间在面试中如果面试官明确要求O(1)空间哈希表就不是首选方案。比如判断数组里有没有重复元素这类题面试官可能会问“空间能不能省”这时候你应该能想到排序后比较相邻元素的方式。第三个坑是过度依赖哈希表的key查询忽略了自定义对象的哈希实现。刷题时我们用的大多是整数或字符串作为key但在工程里如果要用自定义Class作为key就必须正确实现__hash__和__eq__方法否则两个内容相同的对象会被当成不同key。这个点面试官非常喜欢考Day 1可以先留个印象。第四个坑是在Python里用list当作哈希key。Python的list是unhashable类型不能直接作为字典的key。如果你需要用一个数组作为key要转成tuple。我见过不少人在“字母异位词分组”的进阶解法里想用“每个字符的计数数组”作为键结果报错原因就是用了list。5.2 双指针的边界条件和死循环双指针的代码通常很短但边界条件一旦写错要么结果不对要么直接死循环。最常见的错误有两个第一个是while循环条件写错。左右夹逼用的是while left right如果写成while left right在某些题里会让指针重叠后继续操作访问到不存在的数组下标。滑动窗口里的内层循环用while外层用for两种循环混用时尤其要注意left和right的更新是否会导致死循环。第二个是left和right的更新逻辑写反。以盛最多水的容器为例正确逻辑是移动较矮的那一侧。如果你用if height[left] height[right]: left 1那就是移动较高的一侧最终结果一定错误。这类题我建议你在写完代码后用一个简单的测试用例手动在纸上走一遍指针每一步动的位置对不对很快就暴露了。还有一个细节容易在快慢指针题里翻车判断条件里快指针要先判断自己当前节点是否为空再判断下一步是否为空。写成while fast and fast.next是为了防止空指针访问顺序不能反。5.3 刷题第一天最容易被忽略的检查习惯写完代码通过之后大多数新手就直接做下一题了。但实际上面试时最怕的不是你写不出来而是你考虑了不全面。Day 1开始就养成三个检查习惯后面收益很大空输入和单元素输入。很多解法在空数组、只有一个元素时会出现边界越界或返回错误写完后先用这个最简单用例跑一次。全部元素相同的情况。比如移动零的数组全是0三数之和的数组全是同一个数这类极端输入最能检验指针移动逻辑是否健壮。答案不唯一时题目到底要求返回什么。有些题返回下标、有些返回元素、有些要求去重后返回列表返错类型或漏掉去重都会扣分。这三个习惯说起来简单做起来需要刻意练习。我见过太多候选人写完代码后自信地说“没问题”结果面试官补了一个空数组的测试用例代码立刻崩溃。准备面试的过程本质上就是培养这类“对边界的敏感度”。刷完Day 1之后的几句实话最后说点我自己的体会。很多人把刷题当成一件拼意志力的事情今天立flag每天刷三道结果一周后就断了。我自己刷完Hot 100最大的体会是比坚持更重要的是一开始就选对题和节奏。Day 1用哈希和双指针开局是因为它们上手快、反馈强、套路清晰能让你在第一天就尝到“看懂套路→做出题目→理解优化”的正反馈。如果你今天第一次接触这些题目卡住了也没关系把题解看懂、把思路复述一遍、隔天再重刷一遍比一次硬啃十道要有用得多。我第一轮刷两数之和这种题时也看了题解当时还觉得自己很菜等到第四轮再刷Hot 100时很多题已经能闭着眼睛讲思路了。最后再分享一个小技巧把今天做过的题在第二天早上快速浏览一遍代码和记录不用重做只看思路笔记花十分钟就行。这个动作看着不起眼但我实测下来比当天反复刷同一道题的记忆效果更好。希望这份Day 1的总结能帮你少走点弯路明天见。

LeetCode Hot 100刷题第一天：从哈希表与双指针开始

相关推荐

数据库老兵十一年：从Oracle到GaussDB，HCCDE认证全解析

Python超市收银系统实战：从购物车到库存扣减的完整实现

VMware虚拟机安装统信UOS V20 1050e完整教程：从创建到优化

更多资讯

Redwood芯片设计AI：约束驱动的RTL到版图端到端生成原理与工程边界

Python包发布PyPI全流程：ChatGPT对话一键转Markdown工具实战

PINN求解Burgers方程反向问题：调参与实操经验分享

给老工控机装AI牙齿：PCIe转USB 2.0桥接实战

GameDevMind 贡献实战：从图谱文档规范到自动化质量校验的完整工作流

基于Vue+Node的宠物医院管理系统源码拆解与部署实战

今日更新

AWS无服务器应用开发指南：从Lambda到SAM的架构与实践

SpringBoot+Vue人事系统实战：解决HR数据断点与事务一致性

MATLAB手写紧束缚模型计算石墨烯能带结构

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？