Hot100刷题第4天：双指针+哈希+滑动窗口四题拆解

Hot 100刷题进入第4天。按我自己定的节奏这时已经过了“上来就写简单题”的新鲜期开始进入“看着有点思路、一提交就错”的阶段。这篇是从今天开始的记录用内容把当天做的四道题——三数之和、无重复字符的最长子串、移动零、有效的字母异位词——从题目拆解到边界细节完整写一遍。如果你也正在用热题100题单备刷题面试或者刚开始刷题想找一个能直接照抄的复盘模板这四道题的拆解思路都能复用。Hot 100这个题单网上解读很多但真正把每题做透、把同类型题串起来还是得自己过手。第4天我选的题都不算难题都属于“面试高频、写对不容易”的类型也正好把数组双指针、哈希表、滑动窗口这三个最基础的分析套路重新捋了一遍。下面按我当天的记录顺序写代码用Python刷题环境为最常见的判题平台。1. 第4天刷题前的规划与选题逻辑1.1 为什么把“数组双指针哈希”放在第4天很多人刷热题100第一天卡在环境配置第二天被两数之和教育第三天开始怀疑自己是不是不适合写代码。到第四天我反而建议先别急着上难题把“数组里的双指针、哈希表、滑动窗口”这三个最常用的解题模板固定下来。理由很简单热题100里的数组、字符串、链表、二叉树题目有一大半最后都会落到双指针和哈希的组合上。第4天做的题目不需要多么巧妙但都是“面试常客”代码量不大边界条件却很密集。在这个阶段把基础分析姿势练稳后面刷树和图的时候会轻松很多。我给自己定的第4天目标是不看题解、不看评论区独立完成四道题并把每道题的复杂度分析和去重/边界细节写进笔记。建议你也给自己定一个可量化的目标别只写“今天刷几题”而是写“今天能独立讲清楚哪类套路”。1.2 当天的四道题与挑选逻辑我挑的是这样四道题题目核心考点预计用时当天实测三数之和排序 双指针 去重35分钟第一次提交超时第二次通过无重复字符的最长子串滑动窗口 哈希表25分钟边界条件踩坑一次移动零快慢双指针 / 原地操作15分钟一次通过有效的字母异位词哈希计数 / 排序比较15分钟一次通过这个组合的妙处在于它覆盖了双指针的两种方向——三数之和是相向双指针left往右走、right往左走移动零是同向双指针fast往前探路、slow在后面整理。无重复字符的最长子串虽然本质是同向双指针但它和哈希表深度绑定属于滑动窗口大类。字母异位词则是纯粹哈希计数的题用来区分“用哈希优化”和“用哈希做判断”的差别。四道题做完之后可以顺便回答一个问题为什么双指针能降低复杂度因为暴力法会把所有组合都看一遍而双指针通过数组的有序性或单调性把不可能成为答案的分支直接剪掉。2. 三数之和从暴力到双指针2.1 暴力法为什么不可行先看最直白的思路枚举所有三元组判断和是否为0。伪代码就是三层循环枚举 i、j、k。算法复杂度是 O(n^3)。n 稍微一涨比如 n3000循环次数就是 270亿任何判题平台都会超时。暴力法还有一个隐藏问题去重。找到一组 [a,b,c] 之后还要避免出现重复的 a、b、c 组合。如果靠“把结果加入集合再排序去重”虽然能跑出答案但代码写起来很丑复杂度也更高。所以需要一个“在枚举过程中天然不去重”的方案。这就是排序加双指针。2.2 排序 双指针的完整推导先把数组排序这一步的作用有两个。第一排序让数组单调双指针移动方向有了依据。当三数之和小于0说明整体太小left 往右移动让和变大当三数之和大于0说明整体太大right 往左移动让和变小。如果不排序left 和 right 不知道该往哪里走。第二排序让重复元素相邻去重只需比较相邻位置这也是后面所有去重代码的基础。固定第一个数 nums[i]然后用 left 指向 i1right 指向 n-1在剩余区间内找两个数使 nums[left] nums[right] -nums[i]。代码长这样class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: nums.sort() n len(nums) ans [] for i in range(n): # 固定数都大于0后面不可能再凑出0 if nums[i] 0: break # 固定数去重跳过和上一个相同的数 if i 0 and nums[i] nums[i - 1]: continue l, r i 1, n - 1 while l r: total nums[i] nums[l] nums[r] if total 0: l 1 elif total 0: r - 1 else: ans.append([nums[i], nums[l], nums[r]]) # 左指针对应元素去重 while l r and nums[l] nums[l 1]: l 1 # 右指针对应元素去重 while l r and nums[r] nums[r - 1]: r - 1 l 1 r - 1 return ans时间复杂度是 O(n^2)外层固定 i 是 O(n)内层双指针扫描是 O(n)。空间复杂度 O(n)来自排序的栈空间和存储结果一般可以忽略不计。2.3 去重细节三个容易写错的位置这道题最大的坑不是双指针思想而是去重。我第1次提交就是在去重上栽的。第一个位置固定元素的去重。if i 0 and nums[i] nums[i - 1]里的判断是nums[i] nums[i - 1]不是nums[i] nums[i 1]。两者的区别在于如果和第 i1 个数比较会把“同一位置不能重复使用”和“结果不能重复”这两件事混在一起。比如数组是[-1, -1, 0, 1]如果写成nums[i] nums[i 1]第一个 -1 就会被跳过正确答案[-1, 0, 1]就没了。正确写法是当前位置和前一个位置比较而不是和后一个比较。第二个位置找到和为0时的双指针去重。在把[nums[i], nums[l], nums[r]]加入答案之后要先把左指针和右指针移到不重复的位置再执行l 1和r - 1。如果不做这两步就会出现重复结果如果只移动一边又会漏解。第三个位置内层循环结束后外层固定数跳过重复。有些同学会把去重写错顺序导致出现重复三元组。建议顺序是查重、固定、扫描、去重、收缩。多刷几遍之后这三个位置会形成肌肉记忆。3. 无重复字符的最长子串滑动窗口的边界维护3.1 本质维护一个“不含重复字符”的窗口这道题问的是给定一个字符串找出其中最长的、不含重复字符的子串长度。核心思路是维护一个滑动窗口窗口的左边界为 left右边界为 right。right 每次往右走一步同时用一个哈希表记录每个字符最后一次出现的位置。如果 right 指到的字符之前出现过并且位置在窗口内也就是位置大于等于 left那就说明窗口中已经有重复字符了需要把 left 挪到上一次出现位置的下一位。窗口右边界不断前进左边界只前进不后退所以整体时间复杂度是 O(n)每个字符最多被左右边界各访问一次。3.2 逐行拆解与代码这是我当天的最终代码class Solution: def lengthOfLongestSubstring(self, s: str) - int: last_pos {} left 0 ans 0 for right, ch in enumerate(s): if ch in last_pos and last_pos[ch] left: left last_pos[ch] 1 last_pos[ch] right ans max(ans, right - left 1) return ans重点看 left 的更新。例如字符串abbaright0chaleft0ans1right1chbleft0ans2right2chblast_pos[b]1 left0所以 left 更新为 2窗口变成bans2right3chalast_pos[a]0但是0 left2不成立说明这个 a 虽然在之前出现过但已经不在当前窗口内不需要把 left 左移回来。因此窗口变成baans2最后得到答案2正确。如果这里不看位置是否在窗口内直接把 left 挪到011就会把窗口错误地扩张最后算出错误长度。3.3 一个高频错误只看“出现过”却忽略“是否在窗口里”很多人第一次写这道题会写if ch in last_pos: left max(left, last_pos[ch] 1)其实这样也是对的max(left, last_pos[ch] 1)等效于我上面的写法。容易出错的是写成if ch in last_pos: left last_pos[ch] 1这就会把窗口左边界往回拉。比如字符串tmmzuxt这种字符第二次出现在窗口左侧之外的情况往回拉会直接把答案算错。所以要么写成last_pos[ch] left再更新要么用max包一层只要记住窗口左边界只往右移不往左移。另外还要注意ans的更新要放在last_pos[ch] right之后因为 right 已经把当前字符纳入窗口窗口长度是right - left 1。4. 移动零与字母异位词两道被低估的基础题4.1 移动零原地操作与相对顺序题目要求把所有0移动到数组末尾同时保持非零元素的相对顺序并且不能复制数组到额外空间。最容易想到的是“把非零元素直接挑出来再补0”。但这句话说得简单写起来常会犯一个错用remove和append去操作列表。比如这样for x in nums: if x 0: nums.remove(0) nums.append(0)remove的时间复杂度是 O(n)每次删除都会把后面的元素整体前移整体复杂度变成 O(n^2)而且用循环删除0还需要额外处理迭代问题很容易出错。正确做法是同向双指针。一个指针 slow 负责记录“下一个非零元素应该放的位置”另一个指针 fast 负责遍历数组。代码非常短class Solution: def moveZeroes(self, nums: List[int]) - None: slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1这套写法保证了所有非零元素按原顺序放到前面0自然被交换到后面。和 https:// 无关这就是一次典型的“快慢指针原地操作”。有时候也可以先写一遍“前移再补零”的版本# 先把非零元素前移 pos 0 for x in nums: if x ! 0: nums[pos] x pos 1 # 尾部补零 for i in range(pos, len(nums)): nums[i] 0这个版本更容易理解但相比交换版本多了一次整体赋值。两者复杂度都是 O(n)面试时优先写交换版本因为它更符合“原地操作”的语义也显得你更懂双指针。4.2 字母异位词三种解法对比有效的字母异位词是判断两个字符串里的字母种类和数量是否一致。第一种解法排序比较。把两个字符串各自排序如果相等就是异位词。代码好写但复杂度 O(n log n)。第二种解法哈希计数器。分别统计两个字符串中每个字符出现的次数再比较两个计数器是否相等。这是最常用的解法。class Solution: def isAnagram(self, s: str, t: str) - bool: if len(s) ! len(t): return False from collections import Counter return Counter(s) Counter(t)用 Counter 最简洁但面试官有时会问“如果不用 Counter你怎么写”。这时候可以手写一个长度为26的数组class Solution: def isAnagram(self, s: str, t: str) - bool: if len(s) ! len(t): return False cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 for ch in t: cnt[ord(ch) - ord(a)] - 1 return all(x 0 for x in cnt)第三种解法同一位上做“一加一减”再检查是否全为0。本质上和第二种一样只是省掉一个哈希表用数组下标代替定位更快。这道题说“被低估”是因为它是很多变种题的基础。后面常见的“找到字符串中所有字母异位词”就要在滑动窗口里维护这个26长度的计数数组。第4天能把这题的计数和滑动窗口逻辑打通后面就能直接升级。5. 第4天的翻车现场与DEBUG记录5.1 当天遇到的典型错误我如实记录下面这些错我都踩过整理成表格方便你自查。题目错误现象原因分析修复方式三数之和输出结果出现重复三元组固定数去重写成了nums[i] nums[i1]改为nums[i] nums[i-1]三数之和输出结果漏解left 或 right 去重过度去重只在加入答案后执行且用 while 跳过相同元素无重复字符的最长子串窗口左边界被拉回没有判断last_pos[ch] left用last_pos[ch] left或max保护左边界移动零提交超时使用removeappend导致 O(n^2)改为快慢指针交换字母异位词结果错误没有先判断长度不等先if len(s) ! len(t)提前退出再补充一个调试技巧刷题时不要只盯着“通过与否”还要主动构造边界数据。三数之和的[-1, 0, 1, 0]这种多个0的数组、无重复子串的空字符串、全零数组都是很容易暴露问题的用例。5.2 记录用的笔记模板因为标题里写了“记录用”我顺手分享一下我自己用的刷题笔记格式。第4天之后我所有题目都用同一个模板记录复习效率提升非常大。模板分六行日期与手感当天状态、一次提交通过的题目数量题号与考点写清题目属于哪类套路比如“相向双指针/去重”“同向滑动窗口/哈希”复杂度分析时间复杂度和空间复杂度卡住的点可以是一段代码也可以是一句总结错误的输入样例记得把导致错误的用例抄下来类比记忆点用一句生活化的话把解法记住比如三数之和的类比记忆点可以写成“固定一个剩下两个左右夹逼”无重复子串可以写成“右边进来左边不要往回走”。这种笔记模板最大的好处是刷到第30天的时候你要复盘第4天只需要看六行字就能快速回忆起整道题的精髓。6. 给第5天的延续建议与手记第4天结束后我已经把数组、双指针、滑动窗口、哈希这四件套的基础题巩固了一遍。第5天我打算顺理成章进入字符串类目重点看最长回文子串、字符串的排列这类题。其实很多字符串题都会用到第4天的滑动窗口和字母计数相当于旧知识换新包装。如果你和我一样刷题过程中反复卡在同一类边界问题上不需要焦虑。我在实际刷题里发现把“卡住的位置”单独记下来比单纯把题解抄一遍有用得多。第4天我最大的体会是一道题能不能轻松写对关键不在算法多惊艳而在你是否把去重、边界、更新时机这些细节一次想清楚。尤其是滑动窗口的 left 更新我踩坑之后才明白“窗口左边界永远不要回头”这句话是怎么回事。最后一句话给正在刷 Hot 100 的读者热题100题单不是任务清单而是你建立算法分析手感的素材库。别急着赶进度把第4天这种基础组合题吃透后面那些“一看答案就懂、一写就废”的中等题才能真正啃下来。