刷 LeetCode 刷到第 13 天正好撞上“普通数组”这个板块。以前我觉得数组题是最没技术含量的直到被几道题收拾得服服帖帖才明白为什么很多人把这个阶段叫《绝境求生》。所谓“普通数组”指的是那些不需要建树、不需要设计复杂数据结构、看起来就是一组排列好的数字可一旦题目给你加上“O(1) 空间”“不能用除法”“只能遍历一次”这样的限制原本熟悉的 API 全都不让用了难度直接翻倍。这篇文章就记录我第 13 天的刷题过程整理普通数组板块的核心套路包括 238 除自身以外数组的乘积、41 缺失的第一个正数这类高频热题的完整推导以及我踩过的坑和排查方法给正在按热门 100 题刷数组的朋友一份可以直接抄作业的参考。1. 普通数组这个板块为什么称得上“绝境求生”1.1 所谓“普通数组”坑全藏在限制条件里先说个真实感受数组题真正难的从来不是语法而是题目给你的限制条件。LeetCode 热门 100 题里的数组题就是这样题目描述短则三五行例子一看就懂等你动手写解法的时候才发现处处是坑。比如“轮转数组”要求你原地旋转且只用 O(1) 额外空间第一反应肯定是新建一个数组拷贝过去但题目直接把这个路堵死“除自身以外数组的乘积”更狠要求不用除法并且时间复杂度 O(n)于是“先算总乘积再除自身”这种常规想法还没落地就凉了。这种出题方式很像“绝境求生”题目先把你手里最好用的工具没收掉然后看你能不能找到一条不依赖外部存储的路。工程上真实的数组处理场景也一样数据量一大内存和遍历次数就成了命门不可能每次都开一个同样大小的辅助数组。所以这类题考的不是你会不会用数组而是你在资源受限的情况下还能不能组织起一套有效的信息维护方案。理解了这一点再看普通数组板块的高频难题其实都指向同一个问题有限空间、有限时间如何记住你需要的信息。另外我注意到一个现象很多刷题攻略把数组题标成“简单”但简单的是“读写数组元素”难的是“原地”“线性”“值域映射”这一串约束组合在一起。换句话说普通数组不是真的普通它是出题人用来压迫你思维边界的竞技场。你越是想偷懒用现成工具死得越快。1.2 三条主线原地、线性、边界刷完第 13 天的题目我总结出普通数组题的三条主线后面做题几乎都能套上去。第一条主线是“原地”。题目要求不用额外数组那就必须想清楚能不能用原数组本身记录状态反转法、交换法、原地哈希都是这类题的常用解法。它们的共同点是直接把数组当作一块可写可读的内存而不只是只读的数据源。第二条主线是“线性”。时间复杂度要求 O(n)意味着你最多只能做常数次完整遍历不能在每个位置又去翻一遍前面的元素。这就逼着你用“滚动变量”“前缀和/后缀积”“双指针”这类手段把重复计算变成一次性维护。第三条主线是“边界”。数组题最容易出错的地方永远在下标转换、负数、零、越界这些地方。做题时先问自己数组长度是 n元素范围是什么值域和下标能不能建立映射如果元素是负数或者大于 n怎么处理才不会越界三条主线交叉在一起就构成了普通数组题的基本模型在 O(n) 时间、O(1) 空间的限制下通过原地修改或滚动维护正确处理边界条件得出答案。有了这个框架你会发现普通数组板块不再是一堆散题而是有规律可循的类型题。接下来我按通法框架拆解一遍再拿两道硬核真题做完整实操。2. 核心思路拆解数组题的通法框架2.1 先写暴力再按约束条件做减法很多朋友刷数组题容易犯一个毛病拿到题目就拼命想最优解想不出来就卡死。我的做法恰恰相反第一步永远是先写暴力解法哪怕它又蠢又慢。暴力解法的意义是帮你确认自己完全理解题意建立最基本的循环逻辑比如“除自身以外数组的乘积”暴力写法就是两层循环对每个 i 再遍历一遍其他元素求乘积。这种写法时间复杂度 O(n²)肯定过不了但它能让你看清楚重复计算发生在哪里。写完暴力之后再看题目约束开始做减法。以轮转数组为例暴力做法是新开数组逐位拷贝空间 O(n)这时候题目要求 O(1) 空间你就要思考哪些空间可以被省掉答案是用“三次反转法”先整体反转再反转前 k 段再反转后 n-k 段。核心思路就是“数组位置变换可以分解成有限次分段反转”这个思路不需要额外空间而且一次反转只是 O(n) 级别。这背后的逻辑是暴力解法是你的“逃生底线”即使想不出最优解也能保证你写出正确答案而真正的高手不是跳过暴力直接写最优解而是从暴力出发观察时间花在哪、空间浪费在哪然后针对约束逐个优化。我第 13 天做题时每道题都先花一分钟想一遍暴力再决定用哪种优化整体效率反而比直接硬想最优解高很多。2.2 原地修改的黄金法则永远先想覆盖顺序原地修改数组最容易翻车的地方就是覆盖顺序。数组是一个连续内存块当你直接往某个位置写新值时旧值可能已经被覆盖了下一个循环还要用就全乱了。比如经典的“移动零”问题正着遍历时把非零元素前移如果不用交换而直接赋值后面的元素就会被覆盖丢失。处理这类题我的经验是先在脑里跑一遍“最惨情况”——某个位置被写之后还有没有别的地方需要读这个位置的旧值如果有要么从后往前覆盖要么先把旧值暂存到变量里。轮转数组的三次反转法也是覆盖顺序的典型案例为什么先整体反转再分段反转能成立因为它把“每个元素移动 k 位”这个复杂的整体操作拆成了三个局部反转每次反转都是在处理一段连续区间不会出现“覆盖了还没处理完的数据”的问题。覆盖顺序是所有原地数组题的命门写代码前先画一张小数组手工模拟一遍循环比什么注释都管用。2.3 前缀/后缀乘积一个“接力跑”的思维模型238 题除自身以外数组的乘积背后是一个可以复用到很多场景的思维模型把每个位置的结果拆成“左边所有人的贡献”和“右边所有人的贡献”。我在给朋友讲这道题的时候喜欢用接力跑来类比。想象一条环形跑道每个位置的人都拿着一个数字你要算的是“除了自己以外所有人数字的乘积”。这件事最难的地方在于每个位置都要同时知道左边全部人的乘积和右边全部人的乘积。如果比赛是接力跑正方向跑一圈可以顺便记录每个位置左边的累计乘积反方向再跑一圈可以记录右边的累计乘积两边合起来就是答案。工程上实现这个模型有两种做法。第一种是开两个辅助数组 left 和 right正序遍历填 left逆序遍历填 right最后相乘清晰但空间 O(n)。第二种是只用一个结果数组第一遍正序把 left 填进去第二遍逆序维护一个滚动变量 right每到一个位置就把 left 和 right 乘起来写进结果再更新 right。这就是 238 题空间 O(1) 的关键思路。记住“正反两趟跑”这个模型很多类似题目都能用它破题。3. 两道硬核真题实操从读题到 AC3.1 238 除自身以外数组的乘积不能除那就接力先看原题给你一个整数数组 nums要求返回数组 answer其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积并且要求时间复杂度 O(n)不使用除法额外空间复杂度 O(1)。这道题的经典迷惑点是“先算总乘积然后除以 nums[i]”。如果数组里没有 0这个做法完全正确时间复杂度 O(n)空间 O(1)。但题目明确禁止除法而且就算不禁止只要数组里有一个 0整个数组的乘积就变成 0所有非零位置的答案全错。所以必须换思路。我按前缀/后缀积来推。第一步正序遍历一遍让 answer[i] 记录 nums[0] 到 nums[i-1] 的乘积也就是位置 i 左边所有元素的乘积。初始时 answer[0] 1因为第一个元素左边没有任何元素。第二步逆序遍历维护一个变数 right初始值为 1每次把 answer[i] 乘以 right得到最终结果然后 right 再乘以 nums[i]为下一个位置做准备。我拿一个具体例子手算一遍数组是 [1, 2, 3, 4]期望结果是 [24, 12, 8, 6]。第一遍正序answer[0] 1answer[1] answer[0] * nums[0] 1 * 1 1answer[2] answer[1] * nums[1] 1 * 2 2answer[3] answer[2] * nums[2] 2 * 3 6此时 answer 数组是 [1, 1, 2, 6]每个位置存的是“左边乘积”。第二遍逆序right 初始为 1i 3answer[3] 6 * 1 6然后 right right * nums[3] 1 * 4 4i 2answer[2] 2 * 4 8然后 right right * nums[2] 4 * 3 12i 1answer[1] 1 * 12 12然后 right right * nums[1] 12 * 2 24i 0answer[0] 1 * 24 24最后得到 [24, 12, 8, 6]和期望完全一致。这段代码用 Python 写出来非常短def productExceptSelf(nums): n len(nums) answer [1] * n # 第一遍正序填左边乘积 for i in range(1, n): answer[i] answer[i - 1] * nums[i - 1] # 第二遍逆序乘上右边乘积 right 1 for i in range(n - 1, -1, -1): answer[i] * right right * nums[i] return answer注意这里有个细节题目说额外空间复杂度 O(1)是指除了返回的 answer 数组本身之外再开 O(1) 空间answer 数组不算额外空间。这是出题人留给你的“逃生口”一定要看清题目说明很多题都有类似约定。整道题最关键的点就是把“除自身”翻译成“左边乘积乘以右边乘积”只要这个弯转过来代码反而是小事。3.2 41 缺失的第一个正数让数组自己记住出现过的数接下来是 41 题缺失的第一个正数。这题在普通数组板块里属于很有压迫感的一道题目要求给你一个未排序的整数数组 nums找出其中没有出现的最小的正整数并且要求时间复杂度 O(n)额外空间复杂度 O(1)。注意这里连返回数组都不能用了你必须完全在原地完成。第一次看到这题直觉是用哈希集合把所有正数放进 set然后从 1 开始数第一个不在 set 里的就是答案。这个思路时间复杂度 O(n)但空间 O(n)不符合要求。真正的解法是“原地哈希”核心一句话把数组本身当成一个自描述的哈希表让每个位置 i 上存的值恰好表示“i1 这个数是否出现过”。具体做法分两步。第一步遍历数组对于每个位置 i如果 nums[i] 在 [1, n] 范围内且 nums[i] 没有在它应该待的位置就把它交换到正确位置。数字 x 的正确位置是下标 x-1所以当 nums[i] 在范围内就不断和 nums[nums[i]-1] 交换直到当前位置的值无效或者已经归位。第二步再扫一遍数组如果发现某个位置 i 上 nums[i] ! i1那么 i1 就是缺失的最小正整数如果全部位置都合法答案就是 n1。我用 [3, 4, -1, 1] 这个例子手跑一遍。n 4目标是把数组整理成 [1, 2, 3, 4] 的形态即下标 0 放 1下标 1 放 2下标 2 放 3下标 3 放 4。i 0nums[0] 3在 [1, 4] 内正确位置是下标 2nums[2] -1交换数组变成 [-1, 4, 3, 1]继续看 i 0nums[0] -1无效跳过。i 1nums[1] 4正确位置是下标 3nums[3] 1交换数组变成 [-1, 1, 3, 4]继续看 i 1nums[1] 1正确位置是下标 0nums[0] -1交换数组变成 [1, -1, 3, 4]再继续看 i 1nums[1] -1无效跳过。i 2nums[2] 3正确位置就是下标 2已经归位直接跳过。i 3nums[3] 4正确位置就是下标 3已经归位直接跳过。第二次扫描i 0 处是 1i 1 处是 -1不是 2所以缺失的最小正整数是 2答案正确。这里有一个高频踩坑点交换时如果 nums[i] 和 nums[nums[i] - 1] 相等比如数组里有两个重复的 1交换会进入死循环。所以交换前一定要加判断只有当两者不相等时才交换。Python 代码写出来长这样def firstMissingPositive(nums): n len(nums) for i in range(n): while 1 nums[i] n and nums[i] ! nums[nums[i] - 1]: 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这段代码的核心思维转变是我不再依赖外部哈希表去记录“出现过哪些数”而是通过交换让数组自己把信息存储下来。这就是“绝境求生”的本质——当外部资源全被禁止时你只能靠改造已有资源来创造信息载体。理解了这个思维41 题就不再是玄学而是原地哈希的标准应用。3.3 把今天的收获固化成刷题模板第 13 天结束我把普通数组板块的收获整理成三个可复用的模板后面遇到类似题直接套。第一个模板是“读题三问”。拿到任何数组题先问自己能不能排序能不能原地能不能一次遍历如果题目限制 O(1) 空间直接在“原地”这条线上想如果限制 O(n) 时间直接考虑“滚动变量”或者“正反两趟”的模型。这三个问题能帮你快速排除很多低效思路。第二个模板是“原地交换的循环不变量”。凡是要把数组整理成“下标与值对应”的形态都可以用 while 循环加交换实现。关键是无条件记住两点数值范围要判断交换双方不相等才动。这个模板既适用于 41 题也适用于一堆“找重复数”“找缺失数”的变形题。第三个模板是“前缀积/后缀积两趟法”。凡是答案依赖“左右两侧信息的结合”都可以想一想能不能用两趟遍历一趟正序记录一侧信息一趟逆序滚动记录另一侧。这个模型在普通数组、字符串、甚至一些矩阵题里都能迁移。这三个模板配合起来基本能覆盖 LeetCode 热门 100 题里数组板块的大半题型。模板不是死记硬背而是帮你把思考路径固定下来真正做题时只需要根据题目的约束条件做替换。4. 实战避坑与排查技巧实录4.1 高频报错和逻辑失误速查表我把第 13 天做题过程中遇到的高频问题整理成一张速查表每条都是我或身边朋友真实踩过的坑不是网上抄来的理论。典型场景犯错现象根本原因正确姿势238 题误用除法数组含 0 时所有结果错误或除零异常把“不能除”的限制不当回事没考虑 0 的破坏性用前缀积乘后缀积或者先统计 0 的个数分类讨论189 轮转数组忘记取模k 大于数组长度时旋转次数过多结果不对甚至越界没意识到旋转 k 次等价于旋转 k%n 次先执行 k % nums.length再反转41 题交换遇到重复值while 循环死循环程序卡住nums[i] 和 nums[nums[i]-1] 相等时交换无意义导致指针不前进交换前加 if nums[i] ! nums[nums[i] - 1] 判断用元素值直接当下标负数或超大正数导致数组越界忽略了元素值域可能远大于下标范围先判断 1 nums[i] n 再做映射移动零直接赋值覆盖非零元素被覆盖数组数据丢失没考虑覆盖顺序旧值在读之前就被写掉了用快慢指针交换或者从前往后记录非零位置后统一补零这些坑有一个共同特点不是逻辑复杂而是对数组的基本约束没有形成条件反射。我建议每次写完代码都主动检查一遍“我的下标一定在范围内吗”“这个循环一定会在某个时刻终止吗”两句话能挡住绝大多数低级错误。4.2 定位数组题 Bug 的三个步骤如果代码提交通不过先别急着改按下面三个步骤来排查。第一步是手跑小例子找一个三到四个元素的小数组比如 [1, 2, 3] 或者 [3, 4, -1, 1]用纸笔画一下每次循环变量的变化很多时候 bug 一眼就看出来了。第二步是打印关键状态在循环里把 i、当前值、交换位置、临时变量都打出来对照预期找偏差这比盯着代码干想快得多。第三步是问自己三个问题这个下标会不会越界这个循环会不会死循环这个变量代表的意义是不是我理解的那样三个问题问完大部分 bug 都能定位。我印象深刻的一次是 41 题死循环我盯着代码看了十分钟没看出来后来手跑一遍 [1, 1] 才发现 nums[0] 和 nums[nums[0]-1] 相等交换等于原地踏步。从那以后我再写原地交换都会先写判断条件这也成了我固定习惯。4.3 第 13 天关于刷题节奏和复盘的一点体会最后说说刷题节奏。很多人刷 LeetCode 喜欢一天刷十道八道追求数量上的快感但我到第 13 天最大的体会是一天深入吃透两道精选题比泛刷十道题有用得多。普通数组板块的题目之间关联度极高吃透 238 题后面遇到类似的乘积类题目就有底气吃透 41 题原地哈希的套路基本就拿到手了。复盘的时候我习惯按“限制条件”分类而不是按题号分类。比如凡是要求 O(1) 空间的数组题我都记在一起复习的时候只看关键词原地哈希、反转、滚动变量、交换。这样一来下次看到题目里的约束条件马上就能联想到对应的解法家族而不是重新想一遍。另外我强烈推荐一个方法AC 之后把题解逻辑用自己的话讲一遍假装正在给一个完全不懂的人上课。讲不清楚的地方就是你还没真正掌握的地方。我每次都能从“讲不清楚”里发现自己忽略的细节比如 238 题输出数组不算额外空间这种约定如果不是为了讲给别人听很容易一带而过。如果你也在刷 LeetCode 热门 100 题建议你把普通数组板块当成一个整体来攻克先总结套路再逐题验证效率会明显不一样。遇到卡住的地方不用硬扛返回来看这几种思维模型往往能很快找到出路。最后分享一个小技巧我每次 AC 之后会故意给自己的解法“加压”——把额外空间改成 O(1)把双重循环改成单循环把临时变量尽量省掉。这个习惯模拟的正是题目里那种“绝境求生”的状态练久了真正遇到苛刻限制时你就不会慌因为你的思维早就习惯在绝境里找活路了。