很多刷 LeetCode Hot 100 的人会把“普通数组”这个分类放在最后。我一开始也这样心里想的是数组嘛遍历一遍、排个序、换一换位置还能玩出花来直到某天静下心认真把整个分类过完才发现这五道题几乎覆盖了数组题里所有高频考点动态规划、排序扫描、三次反转、前缀积、原地哈希。它们不涉及链表、树、图连堆都不用纯粹靠“怎么操作一个数组”来卡思路。这篇文章就把 Hot 100 里的“普通数组”分类整体拆一遍讲清楚每道题的思路来源、代码细节和容易踩的坑给正在准备算法面试、或者打算系统刷题的朋友一份可以反复查阅的实操笔记。1. “普通数组”分类的真相五道题五种底层思维1.1 先认人Hot 100里的普通数组总共就五道先把这个分类的“成员名单”摆出来方便对照。以下用到的题号都是 LeetCode 官方题号检索起来很方便。题号题目难度核心解法你要练的思维53最大子数组和中等动态规划 / Kadane算法“以 i 结尾”的DP拆解56合并区间中等排序 线性扫描先排序再处理重叠关系189轮转数组简单三次反转 / 额外数组反转操作的组合推导238除自身以外数组的乘积中等左右前缀积两次扫描、空间压缩41缺失的第一个正数困难原地哈希把数组本身当哈希表用看到没有五道题五种风格没有一道是靠背模板能解决的。难度也从简单一路拉到困难所以这个分类绝不是“热身”两个字能概括的。数组本身是最基础的数据结构但正是这种“基础”才最适合考察一个人拆解问题的能力。面试官不需要候选人懂什么高级数据结构就能从这几道题里看出他有没有真正理解算法设计的基本功。1.2 为什么这个分类比看起来重要得多普通数组这一组题目的共同点是不依赖复杂数据结构存储结构就是最简单的连续内存块但每道题都逼着你换一种方式操作它。最大子数组和让你学会把二维的区间枚举压缩成一维的状态转移合并区间让你理解“先排序再扫描”的前提条件轮转数组让你掌握反转操作的组合效果乘积数组让你明白两次扫描如何消除重复计算缺失的第一个正数更狠直接要求你把数组本身改造成哈希表。这也是为什么面试里这些题出现频率很高。数组题写起来快、边界好讨论、解法层次分明特别适合作为面试的“开胃菜”来判断候选人的思维路径。很多人觉得这类题太基础结果一上来就被 41 题卡住原因不是没刷过而是没把这个分类当成一个整体去总结规律。所以我建议刷 Hot 100 的顺序里普通数组应该尽量靠前而不是被跳过。2. 最大子数组和Kadane算法背后的关键视角切换2.1 从暴力枚举到“以 i 结尾”的转念题目一句话给定整数数组nums找出一个具有最大和的连续子数组至少包含一个元素返回其最大和。经典示例是[-2,1,-3,4,-1,2,1,-5,4]答案是 6对应子数组[4,-1,2,1]。几乎所有第一次接触这道题的人第一反应都是暴力枚举枚举所有左端点 i 和右端点 j计算区间和取最大值。如果配合前缀和每个区间的求和可以做到 O(1)但区间总数仍然是 O(n^2) 量级所以在n到几十万的时候完全跑不动。暴力的瓶颈不在于求和而在于“区间”这个对象本身就是二维的。正确的优化思路是把“区间”这个二维对象压缩成一维。定义一个状态dp[i]所有以位置 i 结尾的子数组中和最大的那个子数组的和。这时候你只需要想清楚dp[i]从哪儿来。只有两种可能要么子数组从 i 自己开始也就是单个元素nums[i]要么它延续了“以 i-1 结尾的最佳子数组”变成dp[i-1] nums[i]。于是转移方程非常干净dp[i] max(nums[i], dp[i-1] nums[i])这个视角的价值在于你不需要同时记录左端点和右端点只关心上一个位置能带来的最大“后缀价值”。任何连续子数组问题只要任务目标是“最大和”“最长有效长度”这类极值属性都可以先尝试这种“以结尾位置为状态”的建模方式。2.2 手算过程与边界初值空讲公式不如手算一遍。拿经典示例[-2,1,-3,4,-1,2,1,-5,4]来推inums[i]cur以 i 结尾的最大子数组和res全局最大0-2-2-211max(1, -21)112-3max(-3, 1-3)-2134max(4, -24)444-1max(-1, 4-1)3452max(2, 32)5561max(1, 51)667-5max(-5, 6-5)1684max(4, 14)56你会发现cur 在位置 2 和位置 7 都出现过“负值区间被丢弃、重新开始”的现象全局最大值则一直稳稳记录着 6。代码可以很简洁def maxSubArray(nums): cur nums[0] res nums[0] for i in range(1, len(nums)): cur max(nums[i], cur nums[i]) res max(res, cur) return res这里有两个细节面试官特别喜欢追加提问。第一个是为什么 cur 和 res 的初值必须取nums[0]而不是0因为如果数组全是负数比如[-3, -2]初值为 0 会让 res 永远停留在 0最终错误地返回 0而正确结果是 -2。第二个是题目明确说子数组“至少包含一个元素”所以不能开“空子数组和为 0”的脑洞。理解了这两个边界才算真正掌握 Kadane 算法。2.3 面试讲解顺序先暴力再优化最后证明边界我建议把这类题的答题顺序固定成三步。第一步说暴力枚举所有区间是 O(n^2)不实用。第二步给优化视角改成“以 i 结尾”的状态让当前状态只依赖前一个状态空间可以直接压到 O(1)。第三步主动补一个全负数用例证明初值取nums[0]的合理性。三步走完面试官会觉得你不是背题是真的理解算法的来龙去脉。还有一个常见误区有人把 Kadane 算法归类为贪心理由是“cur 小于 0 就丢到重新开始”。这种解释能过简单版但在进阶版里容易翻车。这个算法本质上是动态规划转移方程恰好等价于那种贪心决策而已。面试时尽量强调 DP 视角因为后面的环形子数组最大和、二维矩阵最大子矩阵等问题都需要在 DP 框架上扩展单纯用贪心语言很难解释清楚。3. 合并区间与轮转数组数组重排类题形的顺序感3.1 合并区间排序先行合并时 end 必须取 max56 题的输入是一组区间比如[[1,3],[2,6],[8,10],[15,18]]要求合并所有重叠区间输出[[1,6],[8,10],[15,18]]。很多人第一反应是“遇到重叠就合并”但真正动手会发现一个尴尬问题如果只用当前区间和下一个区间比较遇到[2,6]在[1,3]后面这种乱序输入就会漏合并。解决办法很简单但也很关键先按区间起点排序。排序之后所有可能重叠的区间一定前后相邻你只需要维护一个“当前合并区间”在扫描过程中不断尝试把它和下一个区间合并或切分。具体逻辑是维护当前合并区间cur [L, R]遍历后续每个区间interval。如果interval[0] R说明有重叠需要合并此时R要更新为max(R, interval[1])。这里是最容易犯错的地方因为如果直接R interval[1]遇到cur [1, 5]和interval [2, 3]这种“完全被包含”的情况R 会从 5 退化成 3结果就错了。正确做法永远是取 max。如果interval[0] R说明当前合并区间到头了把 cur 存入结果再用当前 interval 开启下一轮。循环结束后还有一个 cur 没有处理记得追加。def merge(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) res [] cur intervals[0] for interval in intervals[1:]: if interval[0] cur[1]: cur[1] max(cur[1], interval[1]) else: res.append(cur) cur interval res.append(cur) return res这里有一个 Python 特有的大坑res.append(cur)加入的是引用如果之后你一直原地修改cur已经加入结果集的那个对象也会跟着变造成诡异 bug。上面代码之所以安全是因为后面用了cur interval重新赋值而不是原地改值。如果你习惯用cur[0], cur[1] ...这种写法就要格外小心最好先拷贝一份再存进结果。3.2 轮转数组三次反转是可推导的不是死记的189 题要求把数组整体向右轮转 k 位。最直白的解法是开一个额外数组newArr[(i k) % n] nums[i]然后拷贝回去。这个解法没有任何问题时间 O(n)空间 O(n)。但三次反转法是这道题的灵魂因为它空间 O(1)而且能用一次推导记住不需要背。推导过程拆开看。假设nums [1,2,3,4,5,6,7]k 3。第一步把整个数组反转得到[7,6,5,4,3,2,1]。这一步的效果是原来数组末尾的 3 个元素被搬到了最前面但它们内部顺序是反的。第二步反转前 k 个元素把这一段恢复正确顺序前 3 个变成[5,6,7]。第三步反转剩余的后 n-k 个元素后 4 个从[4,3,2,1]恢复成[1,2,3,4]。最终得到[5,6,7,1,2,3,4]正好是右移 3 位的结果。代码时有一个必须处理的细节k可能大于n因为右移 n 位等价于回到原点所以要先k % n。如果 k 取模后是 0或者数组长度小于等于 1可以直接返回避免反转函数处理空区间报错。def rotate(nums, k): n len(nums) k % n if k 0 or n 1: return def reverse(arr, left, right): while left right: arr[left], arr[right] arr[right], arr[left] left 1 right - 1 reverse(nums, 0, n - 1) reverse(nums, 0, k - 1) reverse(nums, k, n - 1)如果换一下操作顺序会怎样先反转前 k 个再整体反转结果会完全错乱。所以这类题特别讲究操作次序。我第一次写的时候就栽在这里后来养成一个习惯动手前先在草纸上用小例子把每一步之后的数组状态写出来确认反转区间边界没问题再敲代码。这个习惯对轮转类、旋转类题目特别有效。3.3 两题的共同点先想清楚“操作顺序”再写代码合并区间里“先排序后扫描”是正确性的前提轮转数组里“先全局反转再局部反转”的顺序也是正确性的前提。这两道题放在同一个分类里并不是偶然。数组重排类问题本质上是一个状态机每一步操作都在改变后续操作的输入。如果把顺序搞反你在第一步之后就已经失去了正确推导的可能。所以我的经验是遇到“重新组织数组”这类题不要急着写代码先在纸上定义清楚“每一步之后数组变成什么样子”。一旦你能够把每一步的中间状态写出来操作顺序自然就浮出水面了。很多读者觉得“普通数组”里的题不难但写出来总差一口气问题往往就出在顺序感上。4. 乘积数组与缺失正数在原数组上做标记的两种姿势4.1 除自身以外数组的乘积两次扫描、左右相乘238 题要求每个位置输出“除自己以外所有元素的乘积”不能用除法且要 O(n) 时间。如果允许除法第一反应是先算出全部元素的总乘积再逐个除以当前元素。但题目封死了这条路为什么因为数组里可能有 0。一旦有 0除法要么除零报错要么需要特判逻辑又乱又容易出错。标准解法绕开除法反而更通用、更稳健。解法核心非常优雅最终结果里第 i 位的值等于“左侧所有数的乘积”乘以“右侧所有数的乘积”。实现时只需要两次扫描。第一次从左往右用一个变量 left 累计左侧乘积把nums[i]左侧的乘积存进结果数组 res[i]。第二次从右往左用一个变量 right 累计右侧乘积把右侧乘积乘到 res[i] 上。def productExceptSelf(nums): n len(nums) res [1] * n left 1 for i in range(n): res[i] left left * nums[i] right 1 for i in range(n - 1, -1, -1): res[i] * right right * nums[i] return res两个细节必须注意。第一个left 和 right 的初始值必须是 1不是 0否则所有乘积都会被清零。第二个第一轮循环里顺序是“先赋值再乘 left”这样才能保证res[i]存的是严格在 i 左侧的乘积不包含nums[i]自己。如果你把顺序写成“先乘再赋值”结果会把自身也乘进去。这个题面试时经常追问“能不能 O(1) 额外空间”上面代码里的 res 属于输出数组不计入额外空间left 和 right 都是常数空间所以答案是能。4.2 缺失的第一个正数把数组当作哈希表41 题是普通数组分类里最硬核的一道。题目要求找出缺失的最小正整数同时要求时间 O(n)、额外空间 O(1)。这两个限制一放出来排序 O(n log n) 被 banHashSet O(n) 空间被 ban暴力枚举显然也不可能。我第一次刷到的时候盯着题面看了很久觉得这题简直不讲道理。核心洞察就一句话对于一个长度为 n 的数组答案只可能是[1, n1]之间的某个整数。为什么如果 1 到 n 全部出现那答案自然是 n1只要其中任何一个数缺失答案就在 1 到 n 之间。所以完全可以把数组本身当成一张粗糙的哈希表用“下标 i”来记录“数字 i1 是否存在”。最常见的实现是正负标记法。第一遍遍历把所有不在[1, n]范围内的元素统一替换成哨兵值n1。为什么要替换因为后面要按值取绝对值来计算下标如果数组里有 0、负数、或者特别大的正数它们会干扰坐标计算。第二遍遍历遇到一个在[1, n]范围内的值 x就把下标x-1处的元素标记为负数表示“数值 x 已经出现过”。注意这一步必须用abs(nums[i])取原始值因为标记过的位置是负数直接读会得到负数导致下标越界或者逻辑错误。第三遍扫描第一个仍然为正数的下标 i意味着数字 i1 没出现过直接返回 i1如果所有位置都被标记为负说明 1 到 n 全出现返回 n1。def firstMissingPositive(nums): n len(nums) for i in range(n): if nums[i] 0 or nums[i] n: nums[i] n 1 for i in range(n): val abs(nums[i]) if 1 val n: nums[val - 1] -abs(nums[val - 1]) for i in range(n): if nums[i] 0: return i 1 return n 1如果想彻底避开“取绝对值”这一步的纠结也可以用原地交换法把每个在[1, n]范围内的数 x 放到它应该待的位置x-1通过不断交换完成“各归其位”。交换法更直观但 while 循环里的条件要写好必须是nums[i]在[1, n]内并且nums[nums[i]-1] ! nums[i]否则会死循环。我个人推荐先掌握正负标记法因为它在其他“原地哈希”变体里更通用。4.3 普通数组里最容易踩的边界坑汇总这五道题边界条件多我整理了一个自查表刷题前后对照着看非常方便。题目最容易踩的坑应对方式最大子数组和全负数数组cur 和 res 初值取 nums[0]合并区间最后一个区间漏处理循环结束后手动追加合并区间被包含区间导致 end 变小合并时 end 取 max轮转数组k 大于数组长度先k % n轮转数组先局部反转再整体反转必须整体反转在前乘积数组left/right 初始化为 0初始化为 1乘积数组把自身乘进左侧乘积先赋值再乘 left缺失正数数组含 0 或负数干扰下标先统一替换为 n1缺失正数标记过的负数导致下标越界用 abs(nums[i]) 取原始值这些坑看似分散本质上都指向同一个问题对数组下标和变量变化的边界不够敏感。我见过很多刷题不少的人算法思路完全正确最后挂在nums[val-1] -abs(nums[val-1])这种细节上非常可惜。5. 刷题顺序与实战建议五道题怎么变成自己的5.1 推荐顺序由浅入深把思维底座打牢我建议的刷题顺序是189 → 53 → 56 → 238 → 41。理由很简单。轮转数组思路直白能先建立“数组可以被原地重排”的信心最大子数组和让你亲身体验一次关键视角切换这种“原来还能这么想”的感觉特别重要合并区间主要考排序后的扫描逻辑独立完成一遍能帮你建立对“预处理”的敏感度乘积数组是前缀积模式的入门为后续很多二次扫描的题目打基础缺失的第一个正数放在最后因为它是五道题里唯一一道困难题最考验综合能力。如果你时间很紧只能刷三道我建议是 53、56、238。这三道覆盖了动态规划、排序扫描、前缀积三种最常见的数组算法模式而且每道题都值得在十分钟内独立手写一遍。41 和 189 价值也很高但性价比不如这三道突出。当然这只是时间紧张时的取舍正常工作准备面试的阶段五道题都应该吃透。5.2 写代码时的三个自检动作我在刷这些题的过程中总结了一套自检动作每次写完代码不看测试结果先自己在脑子里跑两遍。第一边界用例检查空数组、单元素、全负数、包含 0、k 大于 n、区间端点恰好相等这些都要过一遍。尤其是合并区间[1,4]和[4,5]算不算重叠在闭区间场景下通常算重叠合并成[1,5]。如果你对端点是否重合理解错答案会直接翻车。第二复杂度口头验证。要能准确说出时间复杂度和空间复杂度以及为什么。比如 41 题的交换法while 内部可能发生多次交换很多人以为最坏是 O(n^2)但实际上每次交换都会把一个元素放到它最终的对应位置最多交换 n 次均摊 O(n)。你能点破这一点面试官会很认可。第三主动思考“为什么不能用 XX”。合并区间为什么必须先排序乘积数组为什么不能用除法缺失正数为什么不能开 HashSet这些反证式的问题恰恰是面试官最想听到的内容因为它们证明你不是背答案而是真的理解约束条件。我见过太多候选人最优解甩得飞快但一问“为什么不能用更简单的办法”就哑火这种表现比“慢慢推导到最优解”要扣分得多。5.3 延伸五道题通向的进阶方向普通数组这五道题单独看都是基础但它们全是进阶题的入口。最大子数组和背后是线性 DP吃透之后环形子数组最大和、买卖股票的最佳时机这类变体会顺畅很多合并区间后面连着插入区间、会议室问题考的都是同一条“排序 扫描”的链子轮转数组的三次反转思想可以无缝迁移到矩阵旋转、字符串左移右移乘积数组的两轮扫描是很多前缀和、后缀和题目的原型理解了它以后看到“左边乘右边”这种需求会条件反射缺失正数是原地哈希的代表题类似出现频率很高的“找到所有消失的数字”“数组中的重复数”都在这个框架下。把这几道题刷透再往 Hot 100 的其他分类走你会明显感觉很多题目的底子都能在这一分类里找到影子。这也是为什么我觉得“普通数组”是整个题单里最值得先啃干净的地方。我个人刷完这五道题之后最大的感受是算法题从来没有真正“普通”的分类只有还没被看透的套路。“普通数组”这四个字最容易让人放松警惕但它们恰恰是热点题里最能拉开答题质量的一档。如果你正卡在这个分类不妨按上面的顺序重新过一遍每道题先自己写再对照最优解最后把边界用例反复折磨自己。刷完之后回头看你对数组题的感觉会和之前完全不同。