数组矩阵Hot 100高频题全攻略：哈希表、双指针与原地操作

刷算法题的人应该都有这种感觉Hot 100里的数组和矩阵专题是性价比最高的那部分。题型相对固定、套路清晰、代码量适中而且几乎是所有大厂笔试面试的必争之地。更重要的是数组和矩阵题用的都是最基础的数据结构技巧——哈希表、双指针、前缀和、原地操作摸透了这一块再去啃链表、二叉树、动态规划思路会顺畅很多。这篇文章我会把Hot 100中数组和矩阵相关的高频题做一个横向拆解不按题号流水账式罗列而是按解题套路分类。每一类我都给出了核心思路、代码骨架、复杂度分析、易错点还会分享一些我刷题过程中踩过的坑和总结的经验。如果你正在备战面试或者刚开始刷Hot 100这篇内容可以直接当复习提纲用。1. 专题整体拆解与解题思路1.1 为什么数组和矩阵题如此高频先说个现象我去翻了近几年一些主流公司的笔试面试题库数组和矩阵相关题目的出现频次常年排在所有数据结构里的前三位。原因不复杂——第一数组是最贴近底层的内存结构访问快、实现简单面试官用它来考察候选人对基础算法的掌握程度比上来就甩一道线段树题目要合理得多。第二数组题的解法可以自然过渡到其他专题。比如双指针技巧在链表里也能用哈希表几乎是所有查找类问题的通用解前缀和思路对后续动态规划的优化也有帮助。所以说数组题是算法能力的地基不是没道理的。第三矩阵本身就是二维数组它能把坐标变换方向控制区间划分这类问题包装得更具象适合考察候选人的逻辑拆解能力而不只是背模板。从Hot 100的实际分布来看数组题大概能占到三成上下。你把这部分吃透了等于先拿下了整份题单里性价比最高的一块。1.2 解题方法的选型逻辑数组和矩阵专题看起来题目很多但只要按解题策略归类核心其实就那么几板斧。哈希表用空间换时间。这是解决找目标值判断重复记录出现次数类题的首选方案。比如两数之和如果要暴力解两层循环O(n²)用哈希表能把查找时间压到O(1)整体降到O(n)。代价是多用一个hash map空间O(n)。在一些内存敏感的嵌入式场景里可能要想别的办法但面试场景下哈希表基本就是最优解不用犹豫。双指针用有序性换时间。不管是同向双指针还是相向双指针核心都是利用数组的有序性或单调性避免不必要的重复遍历。比如三数之和排序后配合左右指针可以把O(n³)暴力解直接降到O(n²)。双指针的关键是移动哪个指针这需要结合当前结果和目标值之间的关系来判断。前缀和预处理空间换时间。当题目反复询问某个区间内的和子数组的某种统计属性时前缀和就能把每次区间查询从O(n)降到O(1)。比如和为K的子数组这类题前缀和配合哈希表能在线性时间内解决。原地操作不额外申请数组。矩阵相关的很多题都要求原地旋转原地置零这时候就不能老老实实开辅助数组了。要么找数学规律比如旋转90度可以先转置再加转行要么用标记变量记住关键信息比如原地置零用首行首列做标记。方向模拟处理矩阵遍历顺序。螺旋矩阵、对角线遍历这一类题最直观的思路就是模拟行走的方向用方向数组配合边界检查来约束路径。难点在于边界条件的维护很多初学者栽在已经访问过的格子又被重新访问这种细节上。这些方法不是孤立的实际解题中经常要组合使用。比如最长连续序列就是哈希集合 区间扩展合并区间是先排序再做线性扫描。你把这些套路记熟了看到新题时第一反应不是这题我没见过而是这题属于哪种模式、该用什么策略去套这才是刷题量积累出来的核心能力。2. 高频题型的核心解法与实战细节2.1 两数之和与三数之和两数之和几乎是人人都刷过的题。给定一个数组和一个目标值返回两个下标使它们的和等于目标值。暴力方法就不用说了。用哈希表的话一次遍历就能解决def two_sum(nums, target): seen {} for i, num in enumerate(nums): diff target - num if diff in seen: return [seen[diff], i] seen[num] i return [-1, -1]这里的关键细节是先检查再存入。如果先把当前数字存入哈希表再查找diff当两个数相等且target等于两倍当前数时就会错误地返回同一元素的两个下标。我第一次写的时候就踩过这个坑后来刷多了才发现这是个经典陷阱。三数之和的经典程度不亚于两数之和但它更考验对去重和指针移动的掌控力。要求是找出数组中三个数使它们的和为0而且不能重复。核心思路是排序加双指针def three_sum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if nums[i] 0: break 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: 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 elif s 0: left 1 else: right - 1 return res这个题有三个细节值得重点说一个是排序后如果当前数已经大于0直接终止循环。因为后面的数都更大怎么加都是正数没必要继续。第二个是外部循环的去重。if i 0 and nums[i] nums[i - 1]: continue这行判断的是当前数和前一个数是否相同。注意不能用nums[i] nums[i 1]来判断因为那样会错误跳过形如[-1, -1, 2]这种包含重复元素的合法组合。第三个是内部指针的跳过逻辑。找到一组解后left和right都要移动到不同的值上避免产生完全相同的三元组。这里的两个while循环就是干这个的。顺带提一下四数之和思路完全一样外面套两层循环里面仍然是双指针时间复杂度O(n³)。面试中如果被追问扩展能答上来会很加分。2.2 最长连续序列哈希集合的妙用这个题是看起来很简单但很容易写超时的典型。问题描述很直接给定未排序的整数数组找出最长连续序列的长度。比如[100, 4, 200, 1, 3, 2]最长连续序列是[1, 2, 3, 4]长度是4。最直接的想法是排序后扫描时间复杂度O(n log n)大多数情况下能过。但题目要求O(n)这就得换个思路。突破口是连续序列有唯一起点。一个元素x所在的连续序列如果x - 1不在数组中那么x就是起点。所以我们可以先把所有元素放进哈希集合然后遍历每个元素只对起点进行向后扩展def longest_consecutive(nums): num_set set(nums) longest 0 for num in num_set: if num - 1 not in num_set: cur num length 1 while cur 1 in num_set: cur 1 length 1 longest max(longest, length) return longest这里有个很微妙的地方为什么只从起点开始扩展时间复杂度就是O(n)因为每个元素只会被起点扩展访问一次。它被某个起点扩展到之后它自己作为起点的那轮循环里num - 1 in num_set的判断会直接把它过滤掉不会再进入扩展循环。所以把所有起点扩展过程累加每个元素最多被访问两次总复杂度O(n)。我一开始用了一个很蠢的写法遍历原数组每个元素对每个元素都往两个方向扩展且扩展过程中还真的去修改集合。结果最坏情况下O(n²)在长测试用例上直接超时。后来才想明白不修改集合、只判断起点才是这个题的精髓。2.3 最大子数组和Kadane算法剖析最大子数组和是数组中少数几个一眼看像动态规划、但实际上套路非常固定的题。核心思想可以浓缩成一句话每到一个新的位置决定是从当前位置重新开始还是延续之前的子数组。def max_sub_array(nums): cur max_sum nums[0] for num in nums[1:]: cur max(num, cur num) max_sum max(max_sum, cur) return max_sum这个算法的名字叫Kadane算法思想上等价于一维动态规划dp[i]表示以第i个元素结尾的最大子数组和递推公式是dp[i] max(nums[i], dp[i-1] nums[i])。由于只依赖前一个状态可以滚动优化成上面那个O(1)空间版本。关于这个题有几个值得展开的点第一为什么是cur max(num, cur num)而不是cur num后判断且重置为0因为数组可能全是负数如果你一看到cur变负就重置为0对于[-1, -2, -3]这种输入结果会变成0而正确答案是-1。用max(num, cur num)天然处理了这个边界——cur是负数时num cur num相当于自动选择了从当前元素重新开始。第二这个题可以延伸出很多变种。比如乘积最大子数组因为负负得正的原因需要同时维护最大值和最小值再比如环形子数组最大和需要拆分成内部最大和跨环最大两种情况讨论。面试中常把这两个变种作为追问基础版本理解透了才能举一反三。第三Kadane算法虽然叫动态规划但实际上写起来非常简单这也是为什么它经常会作为热身题出现。我在实际面试中遇到过三次每次都是先让写这个再问变种。第一次没准备充分直接把变种写崩了后来我把这题的变种全部梳理了一遍再遇到就稳了。建议你也把这题当成必刷必熟的级别。2.4 合并区间排序后扫一遍合并区间看起来是个二维数组题实际上解法非常直观。给定一堆区间合并所有重叠区间。先说