LeetCode Hot 100：普通数组题型全解析，双指针与前缀和的正确打开方式

1. 普通数组：Hot 100里最容易被低估的一类题

说实话，每轮刷LeetCode Hot 100的时候，大部分人把精力都砸在二叉树和动态规划上，反而对"普通数组"这一块不太上心。我的看法恰恰相反：Hot 100里普通数组这几道题，是性价比最高、最贴近面试现场的一批题。原因很简单——它们不像图论那样依赖复杂的模板，也不像DP那样需要灵光一现的状态定义，它们考察的是最底层的逻辑拆解能力和对边界条件的敏感度。换句话说，数组题做得好不好，基本能直接反映出一个人的代码基本功扎不扎实。

普通数组一般指那些不涉及特殊数据结构（比如字典树、并查集）的题目，核心操作对象就是一个一维数组。Hot 100里的普通数组题目量不大，但覆盖面很有意思：原地修改、前缀和、区间合并、双指针、哈希辅助，每一种都是后面做中等题、难题的基石。这篇我就把这批题串起来讲，不搞标题党，只聊实际做题过程中值得记录的思路和踩过的坑。

2. 普通数组题型的底层逻辑：先别急着写代码

2.1 为什么数组题最容易"一看就会，一写就错"

数组题的痛点从来不是"不会思路"，而是"思路对了却写不对"。我见过太多人，看到题目第一眼就说"这个我会，用双指针"，结果一运行，要么数组越界，要么结果对不上，最后卡在边界条件上怀疑人生。

数组题的核心难点其实就三个：边界怎么定、原地操作怎么不覆盖还没用的数据、以及循环终止条件怎么描述得干净。这三个问题，恰恰是代码功底的分水岭。

拿最常见的"删除有序数组中的重复项"来说，思路就一句话：双指针，慢指针指向待写入位置，快指针向后扫描。但真正动笔的时候，很多人会纠结：slow初始值应该是0还是1？fast该从哪个下标开始？nums[slow] = nums[fast]之后要不要马上slow++？这些细节看起来小，但每一个都直接影响最终代码的正确性。

我的建议是，数组题别急着盲写，先在草稿纸上画一个具体的数组，把指针移动的每一步都标出来。画完三轮，该有的边界情况基本自己就暴露了。

2.2 方法论：把普通数组题归成四类

Hot 100里的普通数组题虽然各自长得不一样，但归归类就会发现，真正的方法论就那么几种：

第一类是原地状态修改。代表题是"移动零"和"删除有序数组中的重复项"。这类题的内核是"用双指针维护一段有效区间"，考的是对区间定义的理解。

第二类是前缀和与连续子数组。代表题是"最大子数组和"和"和为K的子数组"。这类题的内核是"用前缀和把区间问题转化为差值问题"，一旦想通这一步，很多难题的入口就打开了。

第三类是区间合并与排序。代表题是"合并区间"和"插入区间"。这类题的内核是"先排序，再判断相邻区间的重叠关系"，考的是分类讨论的完备性。

第四类是原地哈希与映射。代表题是"缺失的第一个正数"。这类题最刁钻，内核是"利用数组下标本身作为哈希表，做到O(1)额外空间"。这类思路一旦见过一次，以后再遇到类似题就会形成肌肉记忆。

把这四类想清楚，Hot 100里那几道普通数组题其实已经没有秘密了。

3. 核心题型逐一拆解：每道题都在教你一件事

3.1 移动零：所有双指针题的入门模板

题目要求很简单：把数组里的所有0移动到末尾，同时保持非零元素的相对顺序，要求原地操作。这道题是Hot 100里我推荐所有新手第一个刷的数组题。

原因是它把双指针最核心的思想压缩到了一个极小的场景里。慢指针slow表示"下一个非零元素应该放置的位置"，快指针fast负责向后扫描所有非零元素。整个逻辑就是：快指针找到一个非零值，就把它写到slow的位置上，然后slow前进一位。扫描结束后，slow之后的格子全部填0。

代码非常短：

def moveZeroes(nums): slow = 0 for fast in range(len(nums)): if nums[fast] != 0: nums[slow] = nums[fast] if slow != fast: nums[fast] = 0 slow += 1

注意这里有一个细节值得记录：nums[slow] = nums[fast]之后，如果slow != fast，说明fast位置原本的值已经被写走了，这时直接把它置0，就不需要最后统一补一遍0。这个写法比"先搬完再补0"更省一趟遍历，也更不容易出边界问题。

复杂度上，时间O(n)，空间O(1)，这已经是这道题的极限了。面试时如果写出了额外开辟新数组的版本，基本等于告诉面试官你还没理解"原地操作"这四个字。

3.2 最大子数组和：动态规划的"降维"理解

"最大子数组和"是Hot 100里出场率极高的一道题。题目是给一个整数数组，找具有最大和的连续子数组，返回其和。

这道题我在早期刷的时候，走了一段弯路。当时我用的是暴力遍历，把所有连续子数组的和都求一遍，时间复杂度O(n²)，数据量一上来直接超时。后来看了官方题解才意识到，这道题的朴素动态规划版本理解起来其实很直观：

dp[i]表示以nums[i]结尾的连续子数组的最大和。那么转移方程就一句话——要么把nums[i]接到前面的子数组后面，要么从nums[i]重新开始：

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

这个方程式子短，意义却很深。它其实在表达一个生活化的道理：过去的包袱如果拖累了你，就果断扔掉重新出发。dp[i-1] + nums[i]小于nums[i]，说明前面那段子数组的和是负数，那就不如不要它。

更妙的是，你仔细看会发现，dp数组其实只需要保存前一个状态。所以代码可以压缩成两个变量，空间复杂度直接降到O(1)：

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

这道题我后来在面试里遇到过两次，每次都是作为"热身题"出现。面试官真正想看的，不是你能不能写出这段代码，而是你能不能解释清楚"为什么要用max(cur + num, num)而不是max(cur, num)或者别的组合"。能把这一点说明白，面试官对你这轮的评价基本就稳了。

3.3 合并区间：排序 + 分类讨论的经典组合

合并区间的题目描述很直白：给一堆形如[start, end]的区间，把有重叠的合并成一个区间，返回合并后的列表。

这道题看一眼就知道思路：先按每个区间的起点排序，然后逐个遍历。当前区间的起点如果在前一个合并区间的终点之内，说明有重叠，需要扩展终点；否则就是一个独立的新区间，直接加入结果。

但这里有个我踩过很蠢的坑：排序之后，第一个区间先拿来作为"当前合并区间"，遍历要从第二个区间开始。如果代码里写的是"遍历所有区间并逐个去和结果列表的最后一个比较"，逻辑上其实也是一样的，但很多人一上来把第一个区间也丢进循环里参与判断，就很容易导致result[-1]取到不存在的值。

贴一下我认为最干净的写法：

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

这段代码的巧妙之处在于：每次只和结果列表的最后一个区间比较，因为排过序之后，所有可能的合并行为只会发生在和上一个区间的交接处，不会跨区间合并。想通了这一点，分类讨论就不需要了，一个if就这么写完。

复杂度方面，排序是O(n log n)，遍历是O(n)，总时间O(n log n)，空间O(n)。面试时如果你主动提到"其实可以不用排序吗"这个问题，答案是不行的。合并区间的本质依赖有序性，不排序的情况下需要用其他数据结构维护重叠关系，复杂度只会更高。

3.4 除自身以外数组的乘积：空间复杂度从O(n)到O(1)

这道题的描述是：给你一个数组，返回一个新数组，其中每个位置的值是原数组除该位置以外所有元素的乘积。要求不能用除法，进阶要求空间复杂度O(1)。

不能用除法这点很关键，它直接堵死了"先求全数组的乘积，再逐个除掉当前位置元素"这条路。即使允许用除法，遇到0元素也会让代码写得很狼狈。

正确的解法思路是：把每个位置的答案拆成"左侧所有元素的乘积"乘以"右侧所有元素的乘积"。这个拆法很多第一次接触的人想不出来，但一旦理解了，后面再遇到"类似地拆成两部分"的问题就会思路快很多。

进阶版本的空间复杂度O(1)写法非常有意思。它利用输出数组本身来充当存储：第一趟遍历，从左到右，把每个位置左侧的乘积存入answer[i]；第二趟遍历，从右到左，用一个变量R记录右侧元素的累计乘积，一边更新答案一边更新R：

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

这道题我特别喜欢，是因为它把一个"看起来需要额外O(n)空间"的问题，通过复用输出数组硬生生压缩成了O(1)。这种思维模式，在很多内存敏感的场景下非常有用。做题时可以多想想：输出本身是不是也是一种可用的存储？

3.5 缺失的第一个正数：原地哈希，见过一次就很难忘

"缺失的第一个正数"这道题在Hot 100普通数组里属于那种"第一次见无从下手、看完答案拍大腿"的题。题目要求找未排序数组中最小的缺失正整数，时间复杂度O(n)、空间复杂度O(1)。

我第一次看到"空间O(1)"这个条件时，第一反应是排序。但排序最快也要O(n log n)，直接超时。后来意识到一种操作：既然我们要找的是最小缺失正整数，那答案只可能在1到n+1之间（n是数组长度）。因为如果数组里恰好包含了1到n的所有正整数，那答案就是n+1；否则答案一定在1到n之间。

有了这个范围限制，玩法就多了。可以把数组本身当作哈希表：遍历一遍，把每个在[1, n]范围内的值val放到下标val - 1上。第二遍遍历，如果某个下标i上的值不是i + 1，那i + 1就是缺失的最小正数。如果全部都在，答案就是n + 1。

这个"把值放到对应下标上"的操作，有个专业叫法叫原地哈希。代码实现时有个细节特别注意：交换后，换过来的值可能也落在[1, n]范围内，所以当前下标不能直接前进到下一个，要停在原地继续处理，直到当前位置的值要么不在范围内、要么已经放在了正确位置。很多人的代码卡死，就是少了这个"循环处理"的过程。

4. 实操经验：普通数组题的通用套路与代码习惯

4.1 写数组题前，养成三个好习惯

第一个习惯是先确认边界条件再写循环。空数组、长度为1的数组、全0数组、重复元素最多的数组，这四种情况我都会先在草稿纸上想一遍，或者直接写测试用例跑一跑。很多数组题出错，不是逻辑错了，而是没考虑长度为1的数组在nums[1]上直接越界。

第二个习惯是能用for循环尽量别用while。数组题里for循环天然帮你管理了自增逻辑，能少一个变量就少一个变量。需要用while的场景通常是"当前位置需要重复处理"，比如原地哈希那种情况，这时候用while是对的，但要特别注意防止死循环。

第三个习惯是画图调试，尤其是双指针和滑动窗口。我调试的时候从来不只在脑内推演，而是在纸上写一个具体数组，把指针的位置变化像走表一样走一遍。这个方法朴素，但极其有效。很多"看起来没问题，一跑就错"的代码，用这个方法两步就能找出错在哪。

4.2 关于"改动原数组"的几个实战注意点

普通数组题里，"原地操作"和"允许额外空间"是完全不同的两个设定。用之前一定要看清楚题目要求。如果确实要求原地操作，有几个容易出坑的地方：

一是不要直接覆盖还没读过的数据。比如把非零元素往前挪的时候，如果只做nums[slow] = nums[fast]而不处理nums[fast]的旧值，可能导致后续判断出现错误。这就是为什么我前面给的移动零解法里，特意加了那句if slow != fast: nums[fast] = 0。

二是交换操作往往比赋值操作更安全。很多原地题都可以用swap(nums[i], nums[j])来避免数据覆盖的问题，虽然多了一次操作，但正确性更高。面试时优先保证正确性，再谈优化。

三是注意 Python 的负数下标陷阱。这是个很经典的问题。比如nums[-1]在 Python 里是合法的，取的是最后一个元素。这在遍历时特别容易导致"你以为下标越界了但它没报错，结果结果还不对"。排查数组题 bug 时，如果发现代码没崩但是答案异常，第一时间检查是不是有哪次循环访问了负下标。

4.3 复杂度分析别只背结论，要会现场推导

面试里常规一问是复杂度。很多人张口就来"O(n)"，但面试官一追问"为什么不是O(n²)"就卡住了。数组题的复杂度推导其实很简单，核心就是看每个元素被访问的次数。

双指针类题目，两个指针各自从头到尾走一遍，每个元素最多被访问常数次，所以是O(n)。合并区间里排序占大头，是O(n log n)。原地哈希虽然外层看起来是两层操作，但每个元素最多被交换一次到正确位置，总交换次数不超过n次，所以摊还下来仍然是O(n)。把这些本质看清了，复杂度推导就不再是背题，而是一种自然推理。

5. 常见问题与排查技巧：我踩过的坑，你大概率也会踩

5.1 移动零的常见错误：慢指针没维护好

移动零这道题，最常见的错误版本是这样的：遍历数组，遇到0就把它和后面的非零元素交换。这个思路看起来对，但实现起来会有一个严重问题——你把0往后挪，可能又把一个非零元素往前换，导致非零元素的相对顺序被打乱。这道题明确要求"保持非零元素的相对顺序"，所以用交换的思路稍有不慎就违背题意。

我见过另一种错误是在全部元素都非零时，仍然执行写零操作，白跑一趟还算小事，如果条件判断写成了if nums[fast] == 0而不是!= 0，那整个数组会被清空成全零。写完后建议立刻用[1, 0, 2, 0, 3]这个用例自测一遍，能过基本就稳了。

5.2 最大子数组和的经典误区：默认从下标0开始

很多人做最大子数组和这道题，潜意识里认为"最大子数组一定从开头开始"，于是写出一个不太对的双层循环。实际上最大子数组可能从任何位置开始，比如[-3, -1, -2]里最大子数组和是-1，从下标1开始。如果你默认从开头开始，这道题的边界情况就直接挂了。

另外还有一个小细节：best的初始值不能设成0。因为如果所有数都是负数，正确答案是最大的那个负数（比如-3），而你如果初始值是0，整个代码会直接输出0。正确的初始值是nums[0]，然后从nums[1]开始遍历。

5.3 合并区间最容易漏掉的情况：完全覆盖

合并区间里有一种常见漏网情况：当前区间被合并区间完全包含。举个例子，已经有合并区间[1, 5]，来了一个新区间[2, 3]，正确结果是保持[1, 5]不变。但如果你写的是merged[-1][1] = max(merged[-1][1], interval[1])这行代码，你会发现它天然处理了这个情况——因为3比5小，max 取出来还是5，结果是正确的。

但如果有人写成merged[-1][1] = interval[1]这种直接赋值的写法，合并区间[1, 5]会被错误地改成[1, 3]，结果就错了。这就是我为什么在写合并区间时，反复强调最后一步一定要用max而不是直接赋值。

5.4 原地哈希的难点：交换后不能急着前进

原地哈希这道题写错的人很多，核心原因前面提过：交换到当前下标的值可能仍然不是正确的。举个例子，数组是[3, 1, 2]，第一个位置的值是3，它应该放到下标2上。交换后，下标0变成了原来下标2的值2，而2也应该放到下标1上。如果这时候你把i前进到1，那下标0就漏掉了，最终结果就会错误地算出缺失的正数。

正确的做法是：当前下标不满足条件时，先交换，然后继续处理当前下标；只有满足条件时才让i前进。这个"交换后不前进"的模式，在涉及原地哈希时几乎一定会遇到。建议写这道题之前，先在心里默念三遍：交换后当前下标需要再检查一遍。

5.5 问题排查速查表

6. 从Hot 100看数组题的延伸价值

普通数组这几道题，做完了回头看会发现一个很有意思的现象：它们几乎是为后面所有更复杂的题型做铺垫的。

移动零教会你的双指针维护区间思想，后面在"盛最多水的容器"、"三数之和"里会被反复用到。最大子数组和的动态规划降维写法，是理解"打家劫舍"、"买卖股票的最佳时机"这类题的钥匙。合并区间的排序预处理的思路，在"会议室"、"插入区间"等题目里几乎是同一个套路换皮。原地哈希则更直接，"缺失的第一个正数"只要做透了，后面遇到任何"要求O(1)空间找缺失/重复元素"的题，你都会比别人多想一层。

所以说，普通数组不是"简单题集合地"。它的价值在于用最小的复杂度堆栈，把刷题最底层的几种思维模式密集地过了一遍。把这几道题吃透，比盲目刷50道五花八门的题有用得多。

我个人做这批题还有一个体会：Hot 100里的题目大多不需要什么偏门技巧，每一道都考的是最核心的算法思维。这也是为什么我把这个系列叫做"普通数组"而不是"简单数组"的原因——题目看着普通，背后让你练的东西一点也不普通。

最后分享一个我实际用了很久的做题小习惯：每道题提交通过之后，强制自己用另一种方法重新写一遍。移动零我写过双指针和暴力两种，最大子数组和我用DP和分治各写了一遍，合并区间我试过"扫描线"和"排序后合并"两个版本。这种"一题多解"的训练，比同样时间刷三道新题带来的提升更扎实。批题做多了回头看会发现，很多题真的只是同一个内核换了不同的外壳而已。