0x3f 第24天。先报个流水账：白天几乎没有写自己的代码，时间全泡在“黑马web”课程上，安装环境、配依赖、跑通 demo，真正坐下来敲业务逻辑的时间反而没多少；晚上回到 LeetCode Hot100，终于把“普通数组”这一组题挨个收拾了一遍。如果你也在刷 Hot100，或者正被某个 Web 课程的本地环境折腾得没脾气，这篇应该能对上电波。

1. 普通数组不普通：Hot100分组里的这组题，到底在考什么

1.1 怎么理解“普通数组”这个分组

LeetCode 的 Hot100 题单把题目分成了哈希、双指针、滑动窗口、子串、矩阵、链表这些标签，其中有一个分组就叫“普通数组”。我第一次看到这个分组名字的时候其实挺困惑，什么叫“普通”？是题目简单吗？不是。点进去之后我就明白了，这个“普通”的意思是：这些题不靠某个固定的套路标签，而是需要你结合贪心、排序、模拟、原地哈希等多种思路去解。它们看起来谁都能读懂，但想拿最优解，必须有一点设计感。

这一组题数量不多，但含金量很足。我刷的时候整理了一张表，先放在这里：

刷完这几道题之后我发现，所谓“普通数组”，其实是在考你对数组下标的利用程度。很多优化思路的本质，就是把数组本身当成一个可以重复读写的临时结构，空间越省，题目难度反而越高。

1.2 五道题的共性：状态、排序与原地操作

这五道题看起来毫不相干，但我刷完复盘，发现有三个共同点值得拿出来讲：

第一，几乎每道题都能从“暴力解法”出发。比如最大子数组和可以双层循环枚举所有子数组，合并区间可以两两检查重叠，轮转数组可以每次移动一位。暴力解法写出来很快，但数据量一大就全部超时。这组题真正考验的，是你愿不愿意从暴力解法里站出来，去找那个“多走一步就够得到”的优化方案。

第二，有三道题需要改变数组的“位置关系”。合并区间要排序，轮转数组要反转，缺失的第一个正数要让每个数字回到对应的下标上。数组本身是无序的，但我们需要给它强加一个“逻辑顺序”。这种给数组建立新秩序的过程，和平时搞业务数据完全不是一码事，但两者在思路上是通的。

第三，边界条件极其恶心。空数组、全负数、重复元素、k 大于数组长度，这些情况不做预处理，代码大概率会在某条测试用例上翻车。我自己写的时候，每道题都至少因为边界条件补了一次代码。

1.3 这一组题和 Web 开发的关系

有人可能会问：白天学 Web，晚上刷算法，这不是两条线吗？我自己的感受是，它们并不冲突，甚至离得很近。

白天在“黑马web”课程里折腾的前后端数据交互，本质上就是在处理数组、对象、列表这些数据结构。比如把后端的 JSON 数组经过过滤、映射后渲染到页面上，和刷题时写for循环去变换数组，用的都是同一套逻辑思维。更直白一点：动态规划里的“状态”，对应 Web 开发里的“组件状态”；排序合并数据，对应接口返回数据的预处理。刷题练的是微观能力，Web 课程练的是宏观工程，两个一起学确实累，但脑子不会僵。

2. 白天安了半天程序：Web 课程里的真实时间黑洞

2.1 为什么一个环境能折腾一下午

标题里写着“安了半天程序”，这里说的就是白天最大的感受：很多时候我们不是在写代码，而是在让代码能跑起来。

我白天跟着“黑马web”课程的进度做模拟项目 X，一个后台管理系统的 Demo。按理说课程给的材料已经很完整了，结果卡就卡在环境上：要装一类环境、配置另一类依赖，再启动某个服务，版本稍微对不上就报错。我把网上各种解决办法都试过一遍，有的说升级到某个版本，有的说降低到某个旧版本，还有的直接让你删了重装。

折腾到最后，反而是自己冷静下来，把报错信息从头到尾读了一遍才找到问题：某个配置文件的版本号被写死了，和新装的依赖不兼容。吃一堑长一智：环境问题不是靠“别人怎么说”解决的，是靠“日志怎么报”解决的。

2.2 环境坑位清单与排查顺序

白天踩过的坑不少，趁着还记得，我把自己遇到的典型问题整理成一张速查表，供同样在学 Web 课程的兄弟参考：

我的排查顺序也分享一下：先看报错的第一行日志，而不是最后一行；再确认依赖管理工具的源是否可用；如果一切正常，就清缓存重启；最后才考虑搜错误码。千万不要开一个错误就复制一条命令，那样很容易把环境越修越乱。

3. 晚上刷题：普通数组五连，思路逐个拆

白天把耐心都快耗完了，晚上回到 Hot100 反而觉得脑子清醒不少。下面按我的刷题顺序，把五道题的核心思路逐一拆开讲。

3.1 最大子数组和：Kadane 算法的“负收益不拿”思想

题目要求找一个连续子数组，使它的和最大。暴力解是枚举所有起点和终点，O(n²) 复杂度。我要讲的优化思路，核心其实一句话：如果前面的累加和是负数，那它对后面的子数组就没有任何帮助，果断丢掉。

用一个变量pre表示“以当前元素结尾的最大子数组和”，转移方程是：

pre = max(pre + nums[i], nums[i]) ans = max(ans, pre)

这个方程的意思是：面对nums[i]，你有两个选择——要么把nums[i]接到前面的子数组后面，要么干脆从nums[i]重新开始。哪个大就选哪个。

举一个例子理解：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

• 从1开始，1比-2 + 1大，所以这时候应该从1重新开始；
• 到-3时，-2仍然大于-3，说明可以保留之前的和，往后看看有没有机会转正；
• 到4时，-2 + 4 = 2依然小于4，果断从4重新开始，后面就能一路累积到4 + (-1) + 2 + 1 = 6。

这个思路看着简单，但很多人第一次写容易踩一个坑：初始化ans = 0，结果全负数数组会返回0，而正确结果应该是最大的那个负数。所以ans一定要初始化为nums[0]，或者一个足够小的值。

3.2 合并区间：排序之后，区间重叠就一句话的事儿

题目给一堆形如[start, end]的区间，要求把所有有重叠的区间合并。如果不排序，你可能需要两两比较、反复循环，很容易写乱。排序之后就清爽了：

1. 把所有区间按左端点从小到大排序；
2. 维护当前合并后的区间[L, R]；
3. 遍历下一个区间[a, b]：
   • 如果a <= R，说明两个区间有重叠，把R更新为max(R, b)；
   • 否则，把当前[L, R]加入答案，然后让L = a, R = b。

很多人会下意识觉得“合并区间需要判断四种重叠情况”，但排序之后其实只剩一个判断：新的左端点是否小于等于当前的右端点。等于也算重叠，比如[1,4]和[4,5]应该合并成[1,5]。

3.3 轮转数组：三次反转其实是数学题

向右轮转k个位置，比如[1,2,3,4,5,6,7]转 3 次变成[5,6,7,1,2,3,4]。最直接的办法是用额外数组：

newArr[(i + k) % n] = nums[i]

这个方法很好懂，缺点是空间 O(n)。如果要做到 O(1) 空间，可以用三次反转：

1. 反转整个数组：[7,6,5,4,3,2,1]
2. 反转前 k 个：[5,6,7,4,3,2,1]
3. 反转后 n-k 个：[5,6,7,1,2,3,4]

第一次看到这个解法时，我的反应是“这是什么神仙操作”。其实它背后的数学原因是：向右轮转k次，等价于把序列分成两部分，然后交换这两部分并保持各自内部顺序。反转三次就是在不占用额外空间的情况下完成这个交换。

一定要先执行k %= n，因为k可能比数组长度大，比如数组长度是 7，k = 10，实际效果和k = 3完全一样。如果忘了取模，反转范围可能越界或者说整个数组状态乱掉。

3.4 除自身以外数组的乘积：不让用除法，就左右开弓

这道题的限制很友好：不能使用除法。如果允许除法，思路就变成算总积然后除以每个元素，但那样还要额外处理 0 的个数，反而麻烦。

标准解法分成两趟遍历：

• 第一趟从左到右，用一个变量left累乘已经扫过的元素；
• 第二趟从右到左，用一个变量right累乘已经扫过的元素；
• answer[i]在左乘完的基础上再乘上right。

换句话说，每个位置的结果是“左边的所有元素乘积 × 右边的所有元素乘积”，我们把左右两边分别算好，再乘到一起。

比如[1,2,3,4]：

• 先算左半部分，answer = [1, 1, 2, 6]
• 再从右往左乘，right依次是4, 12, 24, 24，最终得到[24, 12, 8, 6]

这个解法空间 O(1)（不算输出数组），关键是理解前缀积和后缀积是两个独立的累积过程，别把两个方向的变量混在一起更新。

3.5 缺失的第一个正数：拿数组本身当哈希表

这是普通数组里最烧脑的一道。要求 O(n) 时间、O(1) 空间，找一个未排序数组里缺失的最小正整数。难点在于：不能用额外哈希表，却要做到哈希表的查找效果。

核心思路是把数组本身改造成哈希表：长度为n的数组，最多能装下1 ~ n这些正数。所以我们可以让每个下标i上存放值为i + 1的数字。具体做法：

1. 遍历数组，当nums[i]在[1, n]范围内，且nums[i]应该待的位置nums[nums[i] - 1]上不是它自己时，就交换；
2. 交换之后，当前位置可能来了一个新的合法数字，所以要继续判断，直到当前位置不需要再动；
3. 第二次遍历时，如果nums[i] != i + 1，说明i + 1缺失，直接返回；如果全对上了，返回n + 1。

为什么不用普通的if而要用while？因为一次交换只能把一个数送到属于它的位置，但被换回来的数可能还是错位的。举个最简单的例子：[2, 1]，i = 0时nums[0] = 2，应该和nums[1] = 1交换，交换后数组变成[1, 2]，刚好两个数都回位。但如果数组是[2, 1, 0]，交换完0位置后，还要继续检查，所以必须循环处理。

4. 实操过程与核心环节实现：可以直接抄作业版

思路归思路，落地到代码又是另一回事。下面我给出五道题的完整可提交代码，全部基于 C++，注释写在我认为最值得看的地方。代码风格偏竞赛向，但可读性没问题。

4.1 最大子数组和参考代码

class Solution { public: int maxSubArray(vector<int>& nums) { int pre = 0; int ans = nums[0]; for (int x : nums) { pre = max(pre + x, x); ans = max(ans, pre); } return ans; } };

这里有个容易被忽略的点：pre初始化为 0，而不是nums[0]。因为循环内会重新从x开始做一次选择，所以第一次进入循环时pre + x等于x，结果不会受影响。

4.2 合并区间参考代码

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if (intervals.empty()) return {}; sort(intervals.begin(), intervals.end()); vector<vector<int>> ans; int L = intervals[0][0], R = intervals[0][1]; for (int i = 1; i < intervals.size(); ++i) { int a = intervals[i][0], b = intervals[i][1]; if (a <= R) { R = max(R, b); } else { ans.push_back({L, R}); L = a; R = b; } } ans.push_back({L, R}); return ans; } };

vector<vector<int>>默认排序规则是先按第一维升序，第一维相同再按第二维升序，刚好满足要求。最后一步一定要把最后一个区间也加进去，漏掉它是最常见的错误。

4.3 轮转数组参考代码

class Solution { public: void rotate(vector<int>& nums, int k) { int n = nums.size(); if (n <= 1) return; k %= n; if (k == 0) return; reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() + k); reverse(nums.begin() + k, nums.end()); } };

k %= n是必须的。比如nums长度为 1，k随便多大，数组不会改变；如果k刚好是数组长度的整数倍，反转之后又转回原位，等于白做，所以提前返回能省一点时间。

4.4 除自身以外数组的乘积参考代码

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> ans(n, 1); int left = 1; for (int i = 0; i < n; ++i) { ans[i] = left; left *= nums[i]; } int right = 1; for (int i = n - 1; i >= 0; --i) { ans[i] *= right; right *= nums[i]; } return ans; } };

这段代码有两个细节值得注意：第一遍循环后，ans[i]存的是“下标 i 左边所有元素的乘积”；第二遍从右往左乘的时候，ans[i]再乘上“下标 i 右边所有元素的乘积”，正好得到完整结果。如果数组里有 0，代码依然能正确处理，因为它没有使用除法。

4.5 缺失的第一个正数参考代码

class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ++i) { while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { swap(nums[i], nums[nums[i] - 1]); } } for (int i = 0; i < n; ++i) { if (nums[i] != i + 1) return i + 1; } return n + 1; } };

while循环里有个隐藏的终止条件：只有目标位置上的数不等于当前值时才会交换。如果目标位置上已经存在相同的值，说明这个值是重复的，交换没有意义，再循环下去就是死循环。所以判断条件里的!=必须带上。

4.6 测试用例设计

刷题只跑题目给的示例远远不够。我平时测题的标准是：至少准备一组正常数据、一组边界数据、一组极端数据。这五道题我常用的用例也一并列出来：

特别是最大子数组那组全负数用例，很多人不看题就默认答案至少是 0，结果亲手写一遍就会发现，正确答案是-1。

5. 刷题时最容易踩的坑：我的实时排查记录

5.1 边界与初始化问题

普通数组这一组题，十个人里有九个会在边界上翻车。我把自己真实踩到的、以及身边朋友常见的几个问题整理成一张速查表：

这些错误不是不会写，是写太快就容易忽略。我自己解决的办法是：每道题提交前，先盯着循环边界看三秒钟：i是从 0 还是从 1 开始，<=还是<，数组长度是n还是n - 1。

5.2 超时问题：暴力解到最优解的思路跃迁

晚上刷题时，我一开始在最大子数组和上按“暴力”的想法写了一个双循环，小数据没问题，一提交直接超时。后来才意识到，题目给的nums长度可以到 10 的 5 次方甚至更高，O(n²) 必挂。

把双重循环优化成 Kadane 算法的过程，本质上是减少无用功：暴力解法重新计算了大量重复的子数组和，而动态规划只保留“以当前元素结尾”这一种状态，后面的计算就能借助前面的结果。刷这组题最大的收获，不是背下来某个代码，而是记住了优化前先问自己一句：“上一轮的计算结果能不能被这一轮复用？”

5.3 Web 环境问题也在用同样的排查逻辑

白天折腾“黑马web”课程环境，晚上刷算法题，我后来发现在排查思路上它们是一模一样的：报错信息是日志，测试用例是需求，边界条件是环境差异。

白天遇到服务启动不起来，我不能盲目重装，而是去看日志里第一次出现异常的位置；晚上刷题超时，我也不会马上改代码，而是先确认是不是数据规模导致的复杂度问题。万事开头先定位，动手修改要克制，这条经验放到哪里都适用。

6. 第24天，普通数组刷完之后的几点体会

白天安装配置折腾得很疲惫，但晚上把普通数组五连题一张一张做掉之后，我心里反而有种踏实的爽快感。刷题打卡到了第 24 天，一个很明显的变化是：看到题目不再慌张，而是会先往下想一步——这个题暴力能解吗？暴力到底浪费在哪？能不能用下标和交换把空间省下来？

普通数组这一组的名字虽然平平无奇，但题目质量相当能打。它让我把动态规划、排序、反转、前缀积、原地哈希这几种最基础的数组操作又重新练了一遍，而且每一题都有“从暴力到最优”的完整升级路径。白天学的 Web 工程和晚上刷的算法题互相衬托，一个管住宏观工程的思路，一个锻炼微观逻辑的精度，对我来说刚刚好。

最后再分享一个小习惯：我会在每天打卡的最后写下明天计划刷的分组，比如第 25 天准备啃“矩阵”那几道题。预先定好方向，第二天打开题库就不用纠结，直接从任务清单里挑题开刷。你要是也在 Hot100 这条路上，可以试试这个办法，不用贪多，一天五题保持手感，比三天打鱼两天晒网强太多。