我刚开始刷 LeetCode Hot 100 的时候并没把“数组题”放在眼里总觉得数组不就是循环套循环最多再加个排序嘛。直到有一次给一位学弟讲题他随口问我“Hot 100 里的普通数组篇到底在考什么”我卡住了——这才意识到所谓普通数组其实是算法面试里最容易被低估的一类题表面上都是数组实际上把哈希、双指针、动态规划、前缀和、二分、原地操作全串起来了。这篇就把我刷完普通数组篇后留下的东西整理出来既是一份题单复盘也是一份避坑笔记给正在准备面试或者刚开始刷题的读者做个参考。1. 先看清单Hot 100里的“普通数组”到底难在哪1.1 一份我会重点对待的题目清单如果只盯着“数组”这个数据结构会以为它和链表、树比起来简单太多。但 Hot 100 的普通数组题不是让你遍历数组的而是在数组这个最朴素的数据形态上叠加各种算法思想。我自己把和数组直接相关的题挑出来列了个表做题之前先看考点题目核心考点参考时间复杂度两数之和哈希表补偿O(n)三数之和排序双指针去重O(n^2)移动零双指针覆盖/交换O(n)盛最多水的容器双指针单调收缩O(n)最大子数组和一维动态规划/贪心O(n)轮转数组取模三次翻转O(n)除自身以外数组的乘积前缀/后缀乘积O(n)缺失的第一个正数原地哈希O(n)合并区间排序扫描合并O(n log n)搜索旋转排序数组二分有序段判断O(log n)这十道题单独拿出来任何一道都可能出现在面试手写代码环节。它们的共同点不是“数组”本身而是对数组下标、位置关系、修改顺序的理解。说白了普通数组题考的是你能否在空间和时间限制下把对数组的操作做到“刚刚好”。1.2 拿到数组题先问自己三句话刷到后面我养成一个习惯看到数组题先别急着写代码口头确认三件事。能不能改变数组元素的位置如果能排序往往是第一步双指针和合并区间都靠这个如果不能答案多半要依赖哈希表或者前缀信息。问题跟“连续子数组”有关吗如果有关动态规划、滑动窗口、前缀和是主战场如果无关多半是双指针或者二分。空间限制能开到 O(n) 吗能开辅助数组很多题会简单很多如果要求 O(1)就必须考虑原地哈希、翻转、覆盖这些技巧。这三句话帮我避免过很多次“方向错了还硬写”的尴尬。比如“两数之和”如果要求返回原始下标你上来排序就破坏了坐标但如果题目只问是否存在排序加双指针反而更快。同一道题换一个约束解法就完全不同所以先问约束比先背模板重要得多。2. 双指针打法从两数之和到三数之和再到容器题2.1 两数之和为什么哈希表比排序更合适“两数之和”大概是很多人接触的第一道数组题。暴力解法是两层循环复杂度 O(n^2)数据量一大就崩。常见的优化思路是排序后双指针先排序然后用左右指针去找 target。但这里有个关键限制——题目要求返回两个数的原始下标。排序会改变它们的位置所以如果直接用排序双指针你还得额外记录每个元素原来的下标绕了一圈反而麻烦。更适合的做法是哈希表补偿。遍历数组的同时把已经见过的数存进哈希表对当前数 num只需要查 target - num 在不在哈希表里在的话直接返回两个下标不在就把当前数存进去。代码非常短def twoSum(nums, target): seen {} for i, num in enumerate(nums): if target - num in seen: return [seen[target - num], i] seen[num] i return []这个解法的精妙之处在于它把“找另一个数”的问题变成了“查我之前见过没有”的问题时间复杂度掉到 O(n)空间 O(n)。这里有一个容易被忽略的细节不能先把所有元素全部塞进哈希表再开始查找。万一 target 正好等于某个数加它自己比如 nums[3,2,4], target6你如果先塞入全部元素查找时会错误返回 [0,0] 或者把同一个下标用两次。必须边遍历边查确保每个元素只用一次。2.2 三数之和从暴力三重循环到排序双指针“三数之和”是“两数之和”的升级版但解法完全不一样。它要求所有不重复的三元组且三元组内 abc顺序不重复。暴力三重循环 O(n^3) 肯定不行而且去重非常麻烦。正确套路是先排序固定一个下标 i然后在剩余区间 [i1, n-1] 里用左右双指针找两个数。为什么排序后就能用双指针因为数组有序当三数之和小于 0 时说明左指针的数太小左指针右移能让和变大当和大于 0 时说明右指针的数太大右指针左移能让和变小。每一次移动都基于单调性判断而不是盲目枚举所以内层只需要 O(n)整体 O(n^2)。def threeSum(nums): nums.sort() n len(nums) ans [] for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue l, r i 1, n - 1 while l r: s nums[i] nums[l] nums[r] if s 0: l 1 elif s 0: r - 1 else: ans.append([nums[i], nums[l], nums[r]]) while l r and nums[l] nums[l 1]: l 1 while l r and nums[r] nums[r - 1]: r - 1 l 1 r - 1 return ans去重是这题最容易写错的地方。第一层 i 的去重必须写成nums[i] nums[i - 1]然后 continue而不是nums[i] nums[i 1]。如果用后者会直接跳过有效组合比如数组 [-1,-1,2] 中 i0 的 -1 会被当成重复跳过导致一个正确答案都没了。内层双指针找到一组答案后也要把左右指针移动到下一个不同的值再做下一轮搜索。去重的本质是“同一轮搜索中相同数值不重复作为同一个位置”理解了这句话就不容易记错。2.3 盛最多水的容器移动短板背后的单调性“盛最多水的容器”也是双指针但和三数之和的适用条件是两回事。它不需要数组有序只需要两个指针从两端往中间走。面积等于min(height[l], height[r]) * (r - l)每次移动高度较小的那一边。为什么移动短板能保证不错过最优解我当时的理解是面积由短板和宽度共同决定。如果你移动长板新的高度不可能超过原来的短板因为短板还在原处而宽度一定会减少所以面积只可能缩小或者不变这类状态可以直接排除如果你移动短板虽然宽度减少但有概率遇到更高的板把短板高度拉上去面积是有可能增加的。所以每次保留长板、移动短板本质上是在不断排除“不可能成为最优解”的状态而不是在搜索所有状态。最后双指针相遇时留下的最大值就是答案。这道题让我意识到双指针的核心不一定是“有序”而是“决策的单调性”——每次移动都能排除一部分完全不可能的空间。3. 连续子数组问题DP、前缀和、滑动窗口怎么选3.1 最大子数组和以i结尾的状态定义是核心“最大子数组和”是经典的动态规划入门题但很多人一开始会卡在状态定义上。如果定义 dp[i] 为“前 i 个元素中的最大子数组和”转移其实是困难的因为新的子数组需要连续你没法从前 i-1 个元素的最大值直接推出来。换成定义 dp[i] 为“以 nums[i] 结尾的子数组的最大和”转移就非常自然要么自己单独开始一段要么接在 dp[i-1] 后面。所以dp[i] max(nums[i], dp[i-1] nums[i])这个状态定义的精妙之处在于“以 i 结尾”强制把连续性包含进了状态里。因为最后一段必须以 nums[i] 结尾所以它只能由 nums[i] 或 dp[i-1] nums[i] 得到不会出现断开的情况。空间上还可以进一步优化。因为 dp[i] 只依赖 dp[i-1]完全可以用一个变量滚动更新同时用一个全局变量记录历史最大值。这段代码一般叫 Kadane 算法实际运行起来就是线性扫一遍遇到负数先判断它自己开始是否比接上前面的更大。这里我想多说一句很多题目的扩展变体依然是在这个状态定义上做文章比如“允许删除一个元素后的最大子数组和”就要把状态拆成两个没删过元素的最大值删过一个元素的最大值。理解了“以 i 结尾”这个核心扩展题也能很快想通。3.2 除自身以外数组的乘积前缀乘以后缀乘这道题的朴素解法是先算数组所有数的乘积再逐个除但这样立刻会踩进两个坑一是数组里有 0 时除法没法用二是如果面试官要求不能用除法整个思路直接作废。换一个角度位置 i 的答案等于左边所有数的乘积乘以右边所有数的乘积。所以最直观的思路是准备两个辅助数组left[i]从左边扫到 i 的累积乘积right[i]从右边扫到 i 的累积乘积然后答案就是left[i-1] * right[i1]。边界位置需要特殊处理比如位置 0 的左边乘积视为 1位置 n-1 的右边乘积视为 1。更进阶的是空间 O(1) 的做法先用答案数组存一遍“左侧累积乘积”然后再用一个变量从右往左遍历滚动记录右侧乘积边扫边乘。流程大概是def productExceptSelf(nums): n len(nums) ans [1] * n # 第一次遍历ans[i] 左侧所有数的乘积 for i in range(1, n): ans[i] ans[i - 1] * nums[i - 1] # 第二次从右往左用 suffix 记录右侧乘积 suffix 1 for i in range(n - 1, -1, -1): ans[i] * suffix suffix * nums[i] return ans这个解法的核心是“同一块数组空间先存前缀再滚入后缀”理解了就不会把变量搞混。我第一次写的时候在第二次循环里提前修改了 nums结果后缀全乱了。记住第二次循环里改变的是 ans 和 suffix不是 nums。3.3 滑动窗口不是万能药负数和单调性的问题很多人遇到“连续子数组求和”就条件反射般地上滑动窗口但滑动窗口的使用前提是窗口的扩张和收缩具有单调性。最典型的情况是数组元素全部为正数当窗口内元素和大于目标值时右端点继续右移只会让和更大所以只能收缩左端点当和小于目标值时收缩左端点只会更小只能扩张右端点。左右两个指针都只朝一个方向移动复杂度 O(n)。可一旦数组里出现负数单调性就被打破了。窗口和变大不一定来自右移也可能来自左移因为负数带来的影响会让窗口两端都变得“可以双向移动”。这时候滑动窗口就不再高效需要转向前缀和配合数据结构或者用动态规划。我在准备面试的时候给自己立了一条原则看到连续子数组题先看数组里有没有负数。有负数滑动窗口要谨慎全是正数滑动窗口一般就是最优解。4. 空间压缩的艺术原地哈希、翻转法和O(1)技巧4.1 轮转数组取模和三次翻转缺一不可“轮转数组”要求把数组向右轮转 k 位。最无脑的写法是新建一个等长数组把每个元素放到(i k) % n的位置清晰直观也完全正确代价是空间 O(n)。如果要求原地操作三次翻转法是标准答案。三次翻转的思路很漂亮先把整个数组翻转再翻转前 k 个再翻转后 n-k 个结果就是向右轮转 k 位。举个例子nums[1,2,3,4,5,6,7], k3整体翻转[7,6,5,4,3,2,1]翻转前 3 个[5,6,7,4,3,2,1]翻转后 4 个[5,6,7,1,2,3,4]结果完全正确。整个操作只涉及 swap不需要额外数组。但这个题真正的陷阱在 k 上面。k 可能比数组长度大甚至可能是 0。如果不取模直接翻转会越界或者翻转后效果根本不对。正确的第一行操作永远是k % nums.length。每次写这道题我都会刻意提醒自己凡是涉及步数的数组题先取模。这个习惯后来在循环移位、约瑟夫环等问题上也帮我避免了同样的坑。4.2 移动零交换法和覆盖法的取舍“移动零”要求把数组里的 0 移到末尾同时保持非零元素的相对顺序。很多初学者会写类似“遇到 0 就把它冒泡到最后”的代码最差情况 O(n^2)面试官看着都头疼。双指针是正解。我推荐覆盖法而不是交换法用一个 slow 指针指向当前应放置非零元素的位置fast 指针从左往右扫描。fast 遇到非零元素时直接把它赋给 nums[slow]slow 加一扫描结束后从 slow 到数组末尾全部填上 0。代码如下def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow] nums[fast] slow 1 while slow len(nums): nums[slow] 0 slow 1覆盖法比交换法更直白因为它避免了一个容易让新手困惑的场景交换之后裸露出来的 0 可能会再次被 fast 扫描到导致需要额外的跳过逻辑。覆盖法的语义是“先把所有非零元素按序垒过去再统一补零”每一步都很干净。这里还要提醒一句不要用首尾双端交换的方式因为那样会破坏非零元素的相对顺序。移动零要求的是“保持相对顺序”所以指针只能同向移动不能从两头对撞。4.3 缺失的第一个正数把数组本身当成哈希表这道题应该是普通数组篇里最需要背下来的一题因为它足够反直觉。题目要求找出缺失的最小正整数常规做法是开一个哈希表记录出现过的数字从 1 开始往上查空间 O(n)。但面试官如果追加一句“空间 O(1)”很多人就愣住了。原地哈希的思路是数组本身就可以当哈希表。对于一个长度 n 的数组缺失的最小正数一定在 1 到 n1 之间。所以算法的目标是让“值 x”尽量出现在下标 x-1 的位置上。遍历数组只要nums[i]在 [1, n] 范围内且它现在不在正确位置就把它和正确位置上的数交换。交换过来的新数可能依然不是正确位置所以要用 while 循环一直处理。核心代码n len(nums) for i in range(n): while 1 nums[i] n and nums[nums[i] - 1] ! nums[i]: j nums[i] - 1 nums[i], nums[j] nums[j], nums[i] for i in range(n): if nums[i] ! i 1: return i 1 return n 1这个算法的边界条件非常容易踩坑。首先负数和大于 n 的数不影响答案直接跳过其次交换时目标位置已经等于当前值说明这个位置上的数已经正确再交换会死循环最后答案是“第一个不等于下标的数加 1”找不到就返回 n1。我在纸上模拟 [3,4,-1,1] 这个例子跑了一遍才彻底理解为什么交换后还要 while 继续处理。这种把“值映射到下标”的思路后续做“数组中重复数字”“找出消失的数”一类题目时可以反复复用。5. 二分、排序与合并的暗流5.1 搜索旋转排序数组先判断哪一段有序“搜索旋转排序数组”是把一个升序数组在某个未知位置旋转后让你在旋转后的数组里找目标值。乍一看数组不再单调好像没法二分但其实旋转数组有一个很重要的结构特征无论如何旋转从中间切一刀至少有一半是有序的。所以二分的每一步都可以先判断左右区间。如果nums[left] nums[mid]说明左半边有序否则右半边有序。接着在有序的那一半里判断 target 是否落在区间内决定收缩方向。判断有序这部分是核心。代码框架def search(nums, target): l, r 0, len(nums) - 1 while l r: mid (l r) // 2 if nums[mid] target: return mid if nums[l] nums[mid]: if nums[l] target nums[mid]: r mid - 1 else: l mid 1 else: if nums[mid] target nums[r]: l mid 1 else: r mid - 1 return -1边界等号是这题最容易错的地方。判断左半边有序时用nums[l] nums[mid]不能写成否则当区间长度只有 2 时会把有序区间误判成无序。它还涉及一个实际面试中的追问如果数组含有重复元素nums[l] nums[mid]时无法判断哪一边有序这时只能把左指针右移一位继续循环最坏复杂度退化成 O(n)。知道这个退化过程比死记代码更有意义。5.2 合并区间排序之后只剩一个重叠判断“合并区间”看起来和前面的题风格不同但它本质上也是数组题里“先排序再扫描”的典型。思路很简单把所有区间按起点排序用一个pre记录当前合并后的区间逐个遍历后续区间cur。如果cur[0] pre[1]说明两个区间重叠更新pre[1] max(pre[1], cur[1])否则把pre加入结果再把cur设为新的 pre。这题有两个非常隐蔽的错法。第一重叠判断条件不能写成cur[0] pre[1]因为相等也算重叠比如 [1,2] 和 [2,3] 应该合并成 [1,3]。第二更新终点时要用 max不能直接赋值pre[1] cur[1]。我最初用直接赋值遇到区间 [[1,5],[2,3]] 时会错误地输出 [1,3]因为第二个区间完全被包含在第一个区间里它的终点比 pre 小。正确输出应该是 [1,5]。这种“被包含”的情况是测试设计中最容易用来卡人的点。5.3 我不建议背模板建议写“题解卡”数组题的模板化太强强到很多人可以倒背如流但一到变种题就失灵。三数之和的去重条件、轮转数组的取模、缺失正数的 while 交换单独背都能背下来问题是面试时你未必能想起来为什么。我后来给自己规定每做完一道题就在本地笔记里写三句话这道题构造了什么数据结构为什么这样移动指针/更新状态边界条件最容易错在哪写完才发现很多题它们的“为什么”是相互关联的。比如三数之和的双指针为什么能去重和合并区间为什么先排序本质都是在利用单调性剪枝缺失正数的 while 交换和括号匹配里的栈一样都是在维护一个“当前位置正确性”的循环不变量。写题解卡不是为了背答案是为了让自己把零散的经验串成体系。6. 刷完一遍后的避坑清单6.1 我的推荐刷题顺序普通数组篇这几道题我不建议按 Hot 100 默认顺序硬刷因为难度不是线性上升的。我自己的顺序是移动零、两数之和建立双指针和哈希表的基本直觉。三数之和、盛最多水的容器把双指针的“单调性判断”用熟。最大子数组和、除自身以外数组的乘积理解动态规划和前缀信息的拆解。轮转数组、缺失的第一个正数掌握原地操作和空间压缩。合并区间、搜索旋转排序数组把排序、二分这些前置技巧组合进数组题。这样安排的好处是每一组题都复用前面建立的能力不会一上来就被区间合并和旋转数组的边界打懵。6.2 高频错误字段表我把自己和身边朋友最常踩的坑整理成了一张表刷题前扫一眼能避开不少低级错误错误类型出现场景正确应对忘记取模轮转数组k 大于数组长度第一步先k % n去重方向写反三数之和 i 层的去重用nums[i] nums[i-1]判断别用nums[i] nums[i1]相等边界没算重叠合并区间[1,2] 和 [2,3]重叠条件用cur[0] pre[1]更新区间直接用 cur合并区间包含关系终点更新用max(pre[1], cur[1])哈希表一次性全插入两数之和存在相同下标风险边遍历边查查完再插入交换后没有 while 继续缺失的第一个正数用 while 处理交换来的新数直到位置正确这些错误单独看都很简单但组合在一起以后就能很真实地拉开代码能力和“背题能力”的差距。6.3 最后一个小习惯先自问“能不能排序空间能不能开”刷完整个普通数组篇我最大的体会不是哪道题的代码怎么写而是开头那三个问题真的决定了会不会走弯路。很多数组题的光就在“排序是否允许”和“空间是否限制”之间。我面试前练题时每次都会在动手前大声说一句这个数组可不可以排序能不能额外开空间因为一旦把“排序被允许”想明白三数之和可以直接双指针合并区间可以直接扫描一旦意识到“排序会破坏原始下标”两数之和就会立刻转念去想哈希表。一句简单的自问往往能让思路早几秒走上正确的方向。另外一个受用的实操细节是数组题的边界几乎都藏在下标和值的对应关系里。尤其是那些用了“值映射到下标”思路的题拿一组 3 到 5 个元素的小样例在纸上模拟一遍比空想快得多。比如缺失正数我用过 [3,4,-1,1]轮转数组我用过 [1,2,3], k2合并区间我用过 [[1,4],[2,3]]每一个都精准踩中边界模拟完一遍代码正确率明显提升。这些经验说不上多高级但在所有算法题里数组题是最容易通过“自问纸面模拟”提分的类别。如果你也在刷 Hot 100建议从普通数组篇先动手按这里归纳的顺序过一遍再把避坑表贴在抬头能看到的地方效果应该会比你按难度乱刷好很多。