如果你准备面试或者正在刷题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 大于数组长度时比如数组长度是7k是23如果不取模后面翻转的位置全是不对的。顺序上必须先取模再做反转而且取模这一步要在n可能为0的情况下额外加保护虽然 Hot 100 这题一般不会给空数组但养成习惯总没错。第二个是反转区间的边界reverse(0, k - 1)和reverse(k, n - 1)中间的切分点要拿捏准否则 k 为0或等于 n 时第二段和第三段会出现空区间。我当时在这个题上犯了一个印象很深的错误忘记在每次调用reverse前检查 k 是否为0结果 k0 时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(keylambda 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等于把当前位置的前缀和也算进去了导致多计数。这个错误极其隐蔽因为只有 k0 时才会触发普通样例很难暴露。另一个容易忽略的细节是初始化{0: 1}。这个初始化代表“前缀和为0的情况已经出现过一次”它覆盖的是从数组开头到当前这个完整前缀的情况。如果不加这个初始化从 index 0 开始的子数组就漏算了。两道前缀题放在一起刷非常合适一个用的是“前缀积”一个用的是“前缀和”本质都是把区间查询转化为前缀做差再用哈希表优化查找过程。6. 缺失的第一个正数原地哈希6.1 为什么不能排序也不能用额外空间这题是普通数组分区里难度最高的一道也是我最想写的一道。题面很短给你一个未排序的整数数组找出其中没有出现的最小的正整数。要求时间复杂度 O(n)且只能使用 O(1) 额外空间。线性时间 常数空间这个组合几乎封死了所有普通路径。排序是 O(n log n)不能用把数放进set再做范围查询用到了 O(n) 空间不能用额外开一个布尔数组标记出现过的数也不能用。第一次遇到这个题时我瞪着要求看了半天总觉得这种题要么是脑筋急转弯要么是有什么奇技淫巧。答案并不邪门思路是“用数组本身当哈希表”。正整数的最小值是1如果数组长度是 n那么缺失的第一个正数一定落在[1, n1]这个范围内。这就像有 n 个抽屉却要放 n1 个球必然有一个抽屉是空的。我们要做的就是把数组里所有在[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]都出现过答案就是 n1。我第一次做这题时把 while 误写成了 if结果[3,4,-1,1]这个用例跑出来的答案就不对。这里再提醒一下这种“原地归位”类的题目交换之后要重新检查当前位直到当前位要么不是正数、要么已经归位循环才能结束。7. 易错点速查与方法论7.1 数组题的通用套路六道题刷完后我把数组题的常用套路总结成了几条。数组题很少有需要“灵光一现”才能解出来的大多数都可以归入固定模式前缀和/前缀积、双指针、滑动窗口、原地置换、区间排序合并。普通数组分区覆盖了其中大部分。看到一个数组题我建议按这个顺序在脑子里过一遍先想暴力解确认复杂度再想能不能用“前缀”思想减少重复计算然后看空间限制是否允许额外数组如果要求 O(1) 空间再想是不是可以把数组本身当作哈希表或者用双指针原地操作。值得注意的是有些问题表面上是数组题实际可以抽象到其他模型。比如“爱吃香蕉的狒狒”那道题题面是关于吃香蕉的看着像模拟题但实际上是在一个有序的值域上做二分查找。这说明数组题的解法边界非常灵活重要的不是题目标签而是你能否看穿它背后的算法模型。7.2 易错点速查表为了方便回顾我把这六道题的易错点整理成一张表题目常见错误正确做法轮转数组忘记对 k 取模k 为0时再次反转先k % n三段反转区间的端点按 k 切分最大子数组和答案初始化为0全负数数组结果错误ans初始化为nums[0]合并区间合并时直接覆盖右端点忘记取 max合并时用max更新右边界除自身以外数组的乘积没有复用输出数组额外空间超标答案数组先存左积第二遍乘右积和为 K 的子数组先更新哈希表再查表k0时多计数先查表再更新pre[s]初始化{0:1}缺失的第一个正数交换用 if 而非 while索引越界用 while 循环直到当前位置合法或归位检查1xn这张表是我二刷时最重要的复习材料。每次刷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)最后点出哈希表的作用是快速查找前缀差。一套完整的表达下来哪怕代码只写了个大概面试官对印象分一般也不会差。我个人在带新人时发现真正能把这六道数组题讲清楚的候选人写起其他数据结构题目来也普遍更稳。原因很朴素数组题思路少坑却多能在这里保持耐心并总结经验的人面对更复杂的题目时也更容易沉住气。刷完这些普通数组题目之后我最大的感触是算法题难的不是某个高深技巧而是那些藏在代码里的小边界条件。把这些坑都踩一遍并记录下来比盲目追求刷题数量有价值得多。