Hot 100普通数组刷题笔记：六道高频面试题的边界与复杂度解析

如果你准备面试或者正在刷题，LeetCode Hot 100应该是绕不开的一份清单。这份榜单把高频面试题按数据结构分成了十几个分区，其中“普通数组”这一栏很不起眼，题量不大，也不涉及链表、树、图这些复杂结构，但它是我刷了三遍之后回头看得最多的分区。原因很简单：数组是所有数据结构的骨架，普通数组分区里的题，表面上考的是数组操作，实际上考的是边界控制、原地修改和复杂度意识，这些恰恰是现场写代码时最容易翻车的地方。

这篇内容围绕Hot 100里“普通数组”分区的几道核心题目展开，我把每道题的思路演进、代码实现、踩坑记录整理成一份可以直接参考的刷题笔记。适合正在准备技术面试的选手，也适合算法基础薄弱、想在短时间内建立数组题手感的朋友。我自己第一次刷这个分区的时候，六道题里能一次AC的不超过一半，很多错法现在回想起来都非常低级，比如忘了处理负数、没考虑 k 大于数组长度、前缀和哈希表更新顺序写反等。这些问题单独看都很小，但面试的时候每一处都会成为扣分点。

1. 普通数组分区到底在考什么

1.1 这六道题覆盖的核心能力

Hot 100的普通数组分区，不同版本的题单略有出入，但核心的几道题基本固定：轮转数组、最大子数组和、合并区间、除自身以外数组的乘积、和为 K 的子数组、缺失的第一个正数。我一开始看到这个列表时有点困惑，这些题表面上看风格差异很大，有的考贪心，有的考动态规划，有的考哈希表，为什么全被归进“普通数组”？

刷完才明白，它们有一个共同点：都要求在数组这个最简单的基本数据结构上，用最小的额外空间完成任务。无论是反转、区间合并还是原地哈希，本质都在训练同一种能力——在 O(n) 时间和 O(1) 额外空间的约束下，通过有限次遍历和少量变量完成题目要求。

放在面试场景里，这种能力比“会某个算法模板”重要得多。面试官出一道数组题，通常不是想考你背没背过“滑动窗口模板”，而是想看你面对一个看似简单的数组时，能不能敏锐地察觉边界条件，能不能在空间受限的情况下设计出合理方案。

1.2 刷题前的两个约定

进入正题之前，先说两个我给自己定的约定，这也是我二刷三刷时总结的通用原则。

第一个约定，看题先划复杂度要求。题目描述里如果出现“在 O(1) 额外空间”或“不使用额外数组”，这就是最强烈的信号，意味着排序、复制数组这类做法直接出局。如果没写这个限制，也默认先想优化方案，因为面试官通常会追问“能不能不用额外空间”。

第二个约定，边界条件当第一优先级。数组题出错的根源百分之八十来自三种边界：空数组、长度为1的数组、包含负数或零的数组。刷这六道题时，我建议每写完一版代码，先拿这三种输入自测一遍，再提交。后面讲到的每道题里，都能看到边界条件如何影响最终答案。

2. 从轮转数组热身：三段反转法

2.1 题目要点与三种解法对比

轮转数组这题在Hot 100里算比较温和的，题面很简单：给定一个数组，将元素向右轮转 k 个位置。我第一次做的时候很自然地想到复制一份数组，然后按 (i + k) % n 重新填回去，这个解法没有任何问题，时间和空间复杂度都是 O(n)。

但题目的进阶要求是“使用空间复杂度为 O(1) 的原地算法”。这时候就需要想别的办法。我整理了一下，常见的做法有三种：额外数组拷贝、环状替换、三段反转，对比起来非常有意思。

额外数组拷贝是最直觉的思路，适合用来确认题意、写通逻辑，但在空间受限的面试场景中基本不会被认可。环状替换能做到 O(1) 空间，它的核心思想是从某个位置出发，把元素放到它该去的位置，再沿着链条继续替换。这个思路有一个容易踩的坑：当数组长度 n 和轮转步数 k 的最大公约数大于1时，替换会形成多个环，如果只用单层循环，会发现回到起点时还有元素没被处理，调试起来相当费劲。

三段反转法是我最终推荐的做法，代码简洁、逻辑直观、不容易写错。它的步骤只有三步：先把整个数组反转，再反转前 k%n 个元素，最后反转剩余元素。

2.2 三段反转的正确性与易错点

下面是我常用的实现，用 Python 写的话非常短：

def rotate(nums, k): n = len(nums) k %= n def reverse(i, j): while i < j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)

这个方法我第一次看到时，第一反应是“这也能做？”仔细推演一下就理解了：整体反转之后，每个元素的位置变成了 n-1-i，相当于把尾部元素送到了头部，但子区间内的顺序是反的。接下来对前 k 个元素反转，相当于把已经跑到最前面的那部分恢复原始顺序；对剩余元素反转，同理。三次反转合起来，整个数组的轮转效果就完全实现了。

这里有两个细节必须强调。第一个是k %= n，这一行太容易漏。当 k 大于数组长度时，比如数组长度是7，k是23，如果不取模，后面翻转的位置全是不对的。顺序上必须先取模再做反转，而且取模这一步要在n可能为0的情况下额外加保护，虽然 Hot 100 这题一般不会给空数组，但养成习惯总没错。第二个是反转区间的边界，reverse(0, k - 1)和reverse(k, n - 1)中间的切分点要拿捏准，否则 k 为0或等于 n 时，第二段和第三段会出现空区间。

我当时在这个题上犯了一个印象很深的错误：忘记在每次调用reverse前检查 k 是否为0，结果 k=0 时，reverse(k, n-1)实际上把整个数组又反转了一遍，把前面的操作全抵消了。

3. 最大子数组和：动态规划的第一道门槛

3.1 暴力解的问题

最大子数组和这题，题面是找出一个具有最大和的连续子数组。我最早看到这道题时，第一反应是枚举所有起点和终点，就算连续子数组的和。这当然能算出来，但时间复杂度是 O(n²)，在数组长度稍大的情况下直接超时。

暴力解法的问题不在于思路错误，而在于它把大量可以复用的信息丢弃了。枚举所有区间时，每次求和都是从零开始累加，完全没有用上“相邻子数组之间高度重叠”这个特点。凡是有大量重叠计算的地方，就该想想能不能用增量计算或者动态规划来优化。

3.2 DP状态的由来

这个题的动态规划状态定义得很自然。我们设dp[i]为“以nums[i]结尾的最大子数组和”。关键转移方程只有一行：

dp[i] = max(nums[i], dp[i-1] + nums[i])

理解这行式子的方式很直观：对于每个位置 i，要么从nums[i]重新开始一段子数组，要么把nums[i]接到前面的最优子数组后面。这两种情况取较大者，就是当前位置能获得的最大和。

用生活化的类比来说，这就像你在一路捡东西，每个元素是一个物品，有价值也可能付出代价。你手里当前累计的价值如果加上这个物品比直接拿这个物品还低，那就扔掉旧包袱，从这个物品重新开始计算。整个遍历过程中记录下出现过的最大累计值，就是答案。

3.3 一个总会被忽略的初始化细节

实现时有个细节比状态转移本身更容易翻车——初始化。很多版本会把dp数组的初始值设为0，然后遍历时cur = max(cur + nums[i], nums[i])，这本来没错，但如果你把最终答案初始化为0，遇到全负数数组就会得到0，而正确答案是数组里最大的那个负数。

我第一次刷这个题，样例全过了，提交后才被[-1, -2, -3]这种用例打回来。正确的做法是把答案初始化为nums[0]，从nums[1]开始遍历。用滚动变量优化空间时也要保持同样的思路：

def maxSubArray(nums): ans = nums[0] cur = 0 for x in nums: cur = max(x, cur + x) ans = max(ans, cur) return ans

这题学到的思路还可以迁移到很多场景，比如“买卖股票的最佳时机”本质上也是动态规划求最大差值，思路都是相似的：当前状态只依赖前一个状态，空间可以压缩到 O(1)。

4. 合并区间：排序驱动的贪心

4.1 为什么先排序

合并区间的题面是：以数组 intervals 表示若干个区间的集合，合并所有重叠的区间。比如[[1,3],[2,6],[8,10]]里[1,3]和[2,6]有重叠，合并成[1,6]。

这个题我一开始想得很复杂：两个区间可能有包含关系、交叉关系、相离关系，多个区间还可能连环重叠，三个区间一起出现时怎么处理？后来发现，只要先按左端点排序，问题会瞬间简化。

排序的意义在于让区间之间的顺序固定下来。按左端点升序排列后，后一个区间的左端点一定不小于前一个区间，这时判断重叠只需要看前一个区间的右端点和当前区间的左端点。如果前一个右端点 < 当前左端点，说明中间有缝隙，不能合并；否则必然重叠，取更大的右端点作为合并后的右边界。整个过程线性扫描一遍就能完成，排序的 O(n log n) 就是整体复杂度。

4.2 合并细节和两种写法

我常用的写法是先建一个结果数组，遍历时判断是否和结果数组最后一个区间重叠：

def merge(intervals): intervals.sort(key=lambda x: x[0]) ans = [] for l, r in intervals: if not ans or ans[-1][1] < l: ans.append([l, r]) else: ans[-1][1] = max(ans[-1][1], r) return ans

注意合并的条件用的是<而不是<=。当ans[-1][1] == l时，两个区间首尾相接，按题目要求也算重叠，用<会进入 else 分支执行合并，效果是对的。这个细节很容易引起争议，其实两种写法都能过，关键是逻辑上要保持一致。

另一个细节是取max这一步不要省略。写成ans[-1][1] = r是不对的，因为新区间的右端点可能没有前一个区间大，比如[1,10]和[2,3]，直接覆盖会缩短合并后的区间。

如果面试官要求不使用额外数组，可以改用原地更新后调整数组长度的方式，但可读性差一些。我个人建议结果数组在面试时可以放心使用，因为输出本身需要存储，通常额外空间仍算 O(n)，只要不是额外复制整个输入，面试官一般都能接受。

5. 乘积和子数组和：两个前缀思想

5.1 除自身以外数组的乘积：拆成左右两部分

这道题的题面很有迷惑性：给定一个数组，返回一个新数组，其中每个位置 i 的值是原数组中除nums[i]之外所有元素的乘积。它给了两个限制：不能用除法，时间 O(n)，最好空间 O(1)。

不能用除法，很多人会下意识地觉得这题做不了。想想也是，如果允许除法，第一反应就是算总乘积，再除以每个元素。但这个方案有两个破绽：一是除以0会导致崩溃，二是题目根本没给你用除法的权限。

正确的解法是“左右乘积法”。把每个位置的答案看作两部分相乘：左边的所有数乘积和右边的所有数乘积。我们可以先从左往右遍历一遍，用一个数组（或直接复用输出数组）记录每个位置左侧的乘积；再从右往左遍历一遍，用一个变量维护右侧累积乘积，乘到结果上。

def productExceptSelf(nums): n = len(nums) ans = [1] * n left = 1 for i in range(n): ans[i] = left left *= nums[i] right = 1 for i in range(n - 1, -1, -1): ans[i] *= right right *= nums[i] return ans

这个写法的巧妙之处在于利用了输出数组ans来存左半部分信息，空间复杂度符合题目说的 O(1)（不计算输出数组）。我第一次做的时候想用两个额外数组分别存左积和右积，很简单，但不符合进阶要求。后来发现答案数组本身就能当临时存储用，这算是数组题里常见的“复用数组”技巧。

这里有一个值得注意的点：为什么非要两遍遍历？因为“除自身以外”意味着每个位置的信息来源被切成了左右两边，一次遍历只能累积一个方向的乘积，必须左右各扫一次才能覆盖完整信息。

5.2 和为K的子数组：前缀和+哈希计数

和为 K 的子数组这题，题面是统计数组中连续子数组和等于 K 的个数。它和上一题有相似之处：也是求“区间”相关的信息，也有高效的前缀优化方法。

暴力的做法是枚举每个子数组的起点和终点，累加判断是否等于 K，复杂度 O(n³) 或者优化到 O(n²)。这个数据规模一上来就不可行了。

优化思路是转换问题视角。定义前缀和pre[j]为数组前 j 个元素之和，那么子数组[i, j]的和可以表示为pre[j] - pre[i - 1]。我们要找的是pre[j] - pre[i-1] == K，也就是pre[i-1] == pre[j] - K。换句话说，在遍历每个位置 j 时，只需要知道之前有多少个前缀和等于pre[j] - K。

这个统计需求非常适合用哈希表来做。哈希表的键是前缀和，值是这个前缀和出现的次数。每次遍历到一个位置时，先查表统计，再把当前前缀和放入表中。

def subarraySum(nums, k): pre = {0: 1} s = 0 ans = 0 for x in nums: s += x ans += pre.get(s - k, 0) pre[s] = pre.get(s, 0) + 1 return ans

这个题有一个非常经典的坑：更新哈希表的语句必须放在查表之后。如果把pre[s]的更新放在查表之前，那么当k == 0时，s - k == s，等于把当前位置的前缀和也算进去了，导致多计数。这个错误极其隐蔽，因为只有 k=0 时才会触发，普通样例很难暴露。

另一个容易忽略的细节是初始化{0: 1}。这个初始化代表“前缀和为0的情况已经出现过一次”，它覆盖的是从数组开头到当前这个完整前缀的情况。如果不加这个初始化，从 index 0 开始的子数组就漏算了。

两道前缀题放在一起刷非常合适，一个用的是“前缀积”，一个用的是“前缀和”，本质都是把区间查询转化为前缀做差，再用哈希表优化查找过程。

6. 缺失的第一个正数：原地哈希

6.1 为什么不能排序也不能用额外空间

这题是普通数组分区里难度最高的一道，也是我最想写的一道。题面很短：给你一个未排序的整数数组，找出其中没有出现的最小的正整数。要求时间复杂度 O(n)，且只能使用 O(1) 额外空间。

线性时间 + 常数空间，这个组合几乎封死了所有普通路径。排序是 O(n log n)，不能用；把数放进set再做范围查询，用到了 O(n) 空间，不能用；额外开一个布尔数组标记出现过的数，也不能用。第一次遇到这个题时，我瞪着要求看了半天，总觉得这种题要么是脑筋急转弯，要么是有什么奇技淫巧。

答案并不邪门，思路是“用数组本身当哈希表”。正整数的最小值是1，如果数组长度是 n，那么缺失的第一个正数一定落在[1, n+1]这个范围内。这就像有 n 个抽屉，却要放 n+1 个球，必然有一个抽屉是空的。我们要做的就是把数组里所有在[1, n]范围内的数，尽量放到它对应的抽屉里，具体规则是：数字 x应该待在下标 x-1这个位置。

6.2 while交换的实现细节

因为只能原地操作，我们需要把“放错位置”的正数通过交换送回正确位置。这比想象中容易出错，我贴一下我最终稳定通过的版本：

def firstMissingPositive(nums): n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: idx = nums[i] - 1 nums[i], nums[idx] = nums[idx], nums[i] for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1

这个 while 循环有三个重要细节。

第一个，为什么用 while 而不是 if。交换之后，原来的nums[i]被换成了一个新的数，这个数可能还是不属于当前位置，需要继续交换。如果用 if，只交换一次就直接进入下一个位置，会出现很多数字仍然没归位的情况。

第二个，交换前必须检查1 <= nums[i] <= n。小于1的数、等于0的数、大于n的数都不可能在正确位置，直接跳过。如果不做这个检查，写nums[nums[i] - 1]时可能因为nums[i]是负数或超大数导致索引越界，这是我调试时遇到的最常见崩溃原因。

第三个，交换顺序的坑。在 C++ 中如果直接写swap(nums[i], nums[nums[i] - 1])，右侧的nums[i] - 1在求值和交换之间的执行顺序在不同编译环境下可能有差异，最好先存到idx变量。Python 的交换是右侧先求值再统一赋值，相对安全，但养成存idx的习惯可以避免在其他语言里踩同样的坑。

扫描交换结束后，数组里的正数应该“尽可能”待在下标+1的位置。第二次遍历时，第一个nums[i] != i + 1的位置就是答案。如果全部对齐，说明[1, n]都出现过，答案就是 n+1。

我第一次做这题时，把 while 误写成了 if，结果[3,4,-1,1]这个用例跑出来的答案就不对。这里再提醒一下：这种“原地归位”类的题目，交换之后要重新检查当前位，直到当前位要么不是正数、要么已经归位，循环才能结束。

7. 易错点速查与方法论

7.1 数组题的通用套路

六道题刷完后，我把数组题的常用套路总结成了几条。数组题很少有需要“灵光一现”才能解出来的，大多数都可以归入固定模式：前缀和/前缀积、双指针、滑动窗口、原地置换、区间排序合并。普通数组分区覆盖了其中大部分。

看到一个数组题，我建议按这个顺序在脑子里过一遍：先想暴力解，确认复杂度；再想能不能用“前缀”思想减少重复计算；然后看空间限制是否允许额外数组；如果要求 O(1) 空间，再想是不是可以把数组本身当作哈希表，或者用双指针原地操作。

值得注意的是，有些问题表面上是数组题，实际可以抽象到其他模型。比如“爱吃香蕉的狒狒”那道题，题面是关于吃香蕉的，看着像模拟题，但实际上是在一个有序的值域上做二分查找。这说明数组题的解法边界非常灵活，重要的不是题目标签，而是你能否看穿它背后的算法模型。

7.2 易错点速查表

为了方便回顾，我把这六道题的易错点整理成一张表：

这张表是我二刷时最重要的复习材料。每次刷Hot 100，我都会把这类易错点单独记下来，考前只看这张表就能回忆出大部分题目坑在哪里。

7.3 横向联系：数组题不止数组题

普通数组分区做完，不要急着往下走。我建议花一点时间把相关的题横向对比一下，比如“和为 K 的子数组”和“除自身以外数组的乘积”都用到了前缀思想；“缺失的第一个正数”和很多数组类题目一样，本质是在用数组本身做哈希。把这些联系串起来，才算真正把这些题目“刷”透了，而不是“过”了一遍。

8. 刷题过程中的常见问题

8.1 看题解才懂怎么办

很多人做困难题，盯了半小时没思路，忍不住看了题解，看完恍然大悟，然后觉得自己“会了”。第二天再遇到类似的题，又卡住了。这很正常，问题不在看了解析，而在于复盘方式不对。

我的建议是三遍法。第一遍看题解前先自己尝试10到20分钟，把能想到的思路和卡住的地方写下来，哪怕是半成品。第二遍看题解时不要只看代码，重点看解法的第一步是怎么想到的，比如“为什么要排序”“为什么要用哈希表”。第三遍是最关键的：合上题解，第二天在编辑器里从头默写一遍，能独立写出来才算真的理解。

8.2 刷过就忘怎么办

遗忘是刷题过程中最大的敌人，但对抗遗忘有办法。首先，同一道题至少隔一天再写一遍，最好隔三天。第一次做对的题，如果第二遍还能独立AC，才算真正掌握。其次，把每道题的题干和核心思路压缩成一句话记在笔记里，比如“缺失的第一个正数：用数组本身当哈希表，把x放到x-1位置”。复习时先看这句话，想不起来再翻代码。

普通人没有过目不忘的能力，重复是唯一的捷径。我自己第一遍刷Hot 100的数组分区花了大概两周，第二遍只用了三天，第三遍一晚上就能把六道题全部过完，这个提速靠的完全是重复。

8.3 面试遇到原题怎么回答

如果在面试中碰到Hot 100原题，切忌直接背答案。面试官考察的往往不是“你做过没有”，而是你能不能把思路清晰地推导出来。我建议即使知道最优解，也先简单说一句“这题我做过，核心思路是……”然后再展开，让面试官知道你理解原理，而不是背模板。

表达的时候注意说清楚两个点：一是为什么选这个思路，二是复杂度是多少。比如“和为K的子数组”这题，先说暴力枚举是 O(n²)，再说可以用前缀和优化到 O(n)，最后点出哈希表的作用是快速查找前缀差。一套完整的表达下来，哪怕代码只写了个大概，面试官对印象分一般也不会差。

我个人在带新人时发现，真正能把这六道数组题讲清楚的候选人，写起其他数据结构题目来也普遍更稳。原因很朴素：数组题思路少，坑却多，能在这里保持耐心并总结经验的人，面对更复杂的题目时也更容易沉住气。刷完这些普通数组题目之后，我最大的感触是：算法题难的不是某个高深技巧，而是那些藏在代码里的小边界条件。把这些坑都踩一遍并记录下来，比盲目追求刷题数量有价值得多。