刷LeetCode刷到第13天打开题库里的“普通数组”分类我当时的想法很天真——数组题嘛无非就是遍历、排序、双指针能难到哪去。结果当天第一道题就让我见识了什么叫绝境求生。注意这里说的不是题目有多难而是它明明看起来很简单我却连续交了三版代码第一次内存超限第二次时间超限第三次答案是错的。后来我才反应过来“普通数组”这个分类最大的欺骗性就在于“普通”这两个字。它不是考你数组这个数据结构本身而是考你在一个看似线性的结构上能不能做出非线性的抽象。这篇文章把我当天所有翻车和复盘整理的细节写出来给你一份属于Day13的绝境求生手册。如果你也在刷LeetCode时被数组题卡过或者准备面试时需要快速过一遍数组类考法这份梳理应该能直接派上用场。1. 普通数组分类的“温柔陷阱”它真正考的是三种抽象能力“普通数组”其实一点都不普通。点进这个分类题目跨度可以从Easy一路到Hard描述里很少有复杂数据结构出现解法却往往需要你额外维护一张哈希表、一个前缀和数组或者一套精妙的指针移动顺序。暴力解法的第一直觉完全正确但数据范围一上来就超时。这种“题面简单、约束杀人”的风格就是数组题最典型的温柔陷阱。1.1 三种抽象能力拆解我刷完Day13这一批之后把普通数组题真正在考的东西归纳成了三层抽象你可以直接拿这个框架去套后续所有题目。第一层叫历史状态复用。题目要你求某个连续子数组的和、积或计数朴素做法是每次从子数组的左端点重新累加做了大量重复计算。前缀和、前缀积这类技巧的核心就是把“从开头到当前位置”的计算结果存起来把一次区间查询变成两次历史结果相减。第二层叫单调性推导。双指针、滑动窗口之所以能免去一部分无效枚举靠的不是运气而是题目数据满足某种单调性质——要么数组有序要么窗口内的累加和随右指针右移单调递增。没有这个前提你把双指针模板背得再熟写出来也只是看起来对。第三层叫索引与值的重映射。数组题里经常出现“位置本身也是信息”的设定比如轮转数组你要把元素移到(ik)%n的位置颜色分类要把0/1/2三类元素原地分区众数题要求你找到出现次数超过一半的元素。这类题很少依赖复杂结构考的是你愿不愿意在O(1)额外空间的限制下把数组本身当成一个可以反复改写的工作台。1.2 一张表完成题型识别我后来给自己做了一张题型识别表做题时第一件事就是对症下药而不是每次从零开始推暴力解题目症状优先考虑的算法典型代表求连续子数组的和/积等于某值或统计满足条件的子数组数量前缀和/前缀积必要时配哈希表和为K的子数组(560)、除自身以外数组的乘积(238)数组有序或排序后有序找两数关系/最大面积双指针盛最多水的容器(11)求满足条件的连续区间最短长度或数量滑动窗口长度最小的子数组(209)、乘积小于K的子数组(713)区间有重叠需要合并或统计覆盖范围排序线性扫描合并区间(56)要求O(1)额外空间原地修改、原地分类翻转法、荷兰旗、摩尔投票轮转数组(189)、颜色分类(75)另外说一句像腐烂的橘子(994)这类网格题虽然数据也是二维数组但背后的BFS扩散逻辑属于图论不适合混进普通数组专题里硬套数组技巧。分类本身只是手段别被分类束缚住思路。2. 子数组求和与计数的三大进化从暴力到前缀和再到哈希子数组问题是我Day13翻车的重灾区。典型题就是LeetCode 560“和为K的子数组”题面一句话返回数组中和为K的连续子数组的个数。这道题能把暴力解的每一步都伪装得很合理然后在大数据量下让你死得明明白白。2.1 从O(n²)到O(n)的两次跳跃第一版解法是纯暴力。枚举子数组起点和终点对每个区间累加和判断是否等于K。三层循环是O(n³)时间复杂度直接爆炸。稍微聪明一点的做法是维护一个“以i为起点不断累加”的循环也就是枚举起点、延伸终点的同时更新和能把复杂度降到O(n²)但n到10万量级依然不可行。第二版解法是前缀和。先预处理一个数组presum其中presum[i]表示nums[0..i-1]的和。这样任意区间nums[i..j]的和可以表示为presum[j1] - presum[i]。查询一次从O(n)变成O(1)但枚举所有i和j的组合还是O(n²)只是常数变小本质没变。第三版解法才是这道题的精髓。我们换一个等价的视角presum[j] - presum[i-1] K等价于presum[i-1] presum[j] - K。也就是说当我遍历到位置 j 时只需要知道前面有多少个位置 i使得前缀和等于当前前缀和减K。于是哈希表登场把每个前缀和出现的次数记录下来边遍历边查询整体复杂度降到O(n)。from collections import defaultdict def subarraySum(nums, k): pre 0 count 0 seen defaultdict(int) seen[0] 1 for x in nums: pre x if pre - k in seen: count seen[pre - k] seen[pre] 1 return count这段代码有两个极其容易忽略的坑。第一是seen[0]1如果你漏掉这一行所有从数组头部开始、恰好和为K的子数组都会被漏掉因为它们在截断前缀和为0的位置正好是“数组起点之前”。第二是必须先查询再登记。假如你先把当前前缀和pre登记到哈希表里再去查询遇到 K0 的情况会把“长度为0的空子数组”也统计进去导致答案偏大。我第一次写的时候就踩了登记顺序的坑答案多了好几个。2.2 变形题除自身以外数组的乘积前缀和的思路平移到乘积上也一样成立代表作是LeetCode 238“除自身以外数组的乘积”。题目要求返回一个新数组每个位置的值是原数组中除了该位置以外所有元素的乘积并且不允许使用除法。这个限制是出题人故意设的——如果允许除法可以先算总乘积再逐个除但遇到数组里有0就全盘崩溃。所以正解一定是用前缀积配合后缀积。我的写法是先从左到右扫一遍用结果数组存每个位置左边所有元素的乘积再从右到左扫一遍用一个滚动变量right记录右边所有元素的乘积乘入结果数组。这样就实现了时间O(n)、空间O(1)输出数组不算额外空间的解法。def productExceptSelf(nums): n len(nums) res [1] * n for i in range(1, n): res[i] res[i - 1] * nums[i - 1] right 1 for i in range(n - 1, -1, -1): res[i] * right right * nums[i] return res面试里提一句“输出数组不计入额外空间”是很加分的很多人在口述复杂度时忘了这一步明明写出了正确的解法却被追问“你这空间是O(n)啊”白白扣分。此外这个“历史状态复用”的思路在二维前缀和、二叉树路径和里也能平移是普通数组分类里性价比最高的技能没有之一。3. 双指针与滑动窗口为什么有些题能双指针有些题一用就错双指针和滑动窗口是数组题里最容易被滥用的两个技巧。我见过太多人看到“连续子数组”就条件反射地套滑动窗口模板结果在带负数的用例上WA到怀疑人生。判断一个题能不能用这类方法核心标准只有一个数据中是否存在单调性。3.1 双指针的取舍逻辑先拿LeetCode 11“盛最多水的容器”来说。题目是给定一堆高度找两根柱子围出的最大面积。暴力解O(n²)枚举每对柱子数据量一大必超时。双指针做法是让左右指针分别指向数组两端每次移动高度较小的那一侧。为什么敢移动短边因为容器面积由较短的那根柱子决定。如果固定短边、移动长边面积只可能变小底边变短高度不会超过短边所以短边所在的这一侧无论如何都无法产生更优解可以直接排除。每次移动都排除掉一个“不可能成为答案”的状态双指针才能在O(n)内收敛。def maxArea(height): left, right 0, len(height) - 1 ans 0 while left right: area min(height[left], height[right]) * (right - left) ans max(ans, area) if height[left] height[right]: left 1 else: right - 1 return ans这个题的循环条件用left right而不是left right原因很简单两根柱子必须存在间距当指针重合时计算出来的“容器”是零宽度没有意义。这个细节在任何“对向双指针”题型里都适用。3.2 滑动窗口的边界语义滑动窗口类题目的代表是LeetCode 209“长度最小的子数组”。题目说数组里全是正整数求满足和大于等于target的最短连续子数组长度。这里的关键前提就是“全是正整数”四个字它保证了窗口和随着右指针扩大单调不减左指针收缩时才不会破坏正确性。def minSubArrayLen(target, nums): left 0 total 0 ans float(inf) for right in range(len(nums)): total nums[right] while total target: ans min(ans, right - left 1) total - nums[left] left 1 return 0 if ans float(inf) else ans反过来如果数组里存在负数窗口和就不再单调右指针右移时总和可能变小。这时你再拿“while total target就收缩左边界”的模板去写必然出错——你可能会在一个右边界还没走到正确位置的中间态上提前收缩丢掉最优解。正确的做法是回到前缀和哈希的思路。这个坑在讨论区里反复出现属于典型的“背模板翻车”现场。滑动窗口里还有一个让人头大的细节是子数组计数。LeetCode 713“乘积小于K的子数组”要求统计乘积小于K的子数组总数当右指针扩展到位置right时以right结尾的满足条件的子数组数量是right-left1。这个式子的直观含义是左边界可以取left到right之间的任意一个位置每个左边界都对应一个不同的子数组。很多人把这里的1丢掉导致统计结果少了一大截。4. 合并区间与原地变换在“可读性”和“极致空间”之间做选择普通数组分类里还有一批题表面上是在处理数据本身实际上是在考验你“操作顺序”的设计能力。合并区间和原地变换就是这一类的两个极佳代表。4.1 合并区间为什么不用原地修改LeetCode 56“合并区间”是面试高频题。输入是一堆形如[start,end]的区间要求把所有重叠区间合并后输出。正解思路非常固定先对所有区间按起点排序保证重叠区间一定相邻然后线性扫描用一个结果数组维护当前合并后的区间。如果当前区间和结果数组最后一个区间不重叠直接加入否则更新最后一个区间的上限为两者较大值。def merge(intervals): intervals.sort(keylambda x: x[0]) res [] for interval in intervals: if not res or res[-1][1] interval[0]: res.append(interval) else: res[-1][1] max(res[-1][1], interval[1]) return res有些人在刷题时习惯性地追求极致空间会想“能不能不建res直接在原数组上改”。我试过结果修bug修到暴躁。原因很简单排序本身已经消耗了O(n log n)额外O(n)的存储完全在可接受范围内原地修改会让代码里充满了数组写入和引用修正可读性断崖式下降。面试官真正想看你的是“能不能讲清楚什么时候该合并、什么时候不该合并”而不是你能否省掉一个数组。这个道理在真实工程里也一样可读性优先性能等到瓶颈处再优化。4.2 翻转法和荷兰旗原地变换的两个代表原地变换题里最值得吃透的是LeetCode 189“轮转数组”。题目要求把数组往右轮转k步且只能用O(1)额外空间。经典做法是三次翻转先整体翻转再翻转前k个再翻转后n-k个。比如[1,2,3,4,5,6,7]往右轮转3步整体翻转后变[7,6,5,4,3,2,1]翻转前3个变[5,6,7,4,3,2,1]再翻转后4个得到[5,6,7,1,2,3,4]完美。def rotate(nums, k): n len(nums) k % n nums.reverse() nums[:k] reversed(nums[:k]) nums[k:] reversed(nums[k:])这里最经典的翻车点是忘记对 k 取模。如果数组长度是2、k是3不取模的话翻转操作会把数组搅成一团乱麻。取模这一步不是数学仪式而是把你的翻转范围限定在实际有效的位移量内。另一个必练题是LeetCode 75“颜色分类”要求把包含0、1、2的数组原地排序且不能调用排序库。标准解法是荷兰旗三指针一个指针p0维护0的右边界一个指针p2维护2的左边界一个当前指针cur从头扫描。遇到0就和p0交换p0和cur都前进遇到2就和p2交换只把p2左移遇到1直接跳过。def sortColors(nums): p0, p2, cur 0, len(nums) - 1, 0 while cur p2: if nums[cur] 0: nums[p0], nums[cur] nums[cur], nums[p0] p0 1 cur 1 elif nums[cur] 2: nums[p2], nums[cur] nums[cur], nums[p2] p2 - 1 else: cur 1注意遇到2交换后cur不能直接加1因为换过来的元素可能是0需要下一轮继续处理而遇到0交换后cur可以加1因为从左边界换过来的元素只可能是已经扫描过的1。这个不对称性就是荷兰旗题最容易写错的地方。5. 边界条件排查清单我在数组题里翻过车的五种用例数组题真正的绝境不是想不出思路而是思路完全正确却因为一个边界用例反复提交。我整理了五种最高频的翻车场景全部来自Day13当天的真实经历。5.1 五种极端用例复盘第一种是空数组和单元素数组。很多在你脑子里完美运行的解法一遇到空数组就直接越界。比如在初始化res[0]1之前没有判断len(nums)0或者滑动窗口初始化left0, right0后直接访问nums[right]而数组根本是空的。写代码前先看一眼输入约束有没有给数组长度的下限。第二种是全部元素相同。这类用例专治各种“假设元素分布均匀”的隐含前提。比如摩尔投票法求众数如果数组只有两个元素且不同候选人的切换逻辑必须保证最后能正确输出“不存在众数”的语义荷兰旗法在全部是0的数组里p2的初始化必须够大否则交换时会触发越界。第三种是极大极小值。前缀和或前缀积的中间结果可能溢出int。我刷题时习惯先用Python因为没有int溢出烦恼但换到C或Java就得非常小心。LeetCode很多题目都暗示过“结果保证在32位整数范围内”但中间量可不一定该用long long的地方别逞强。第四种是数组包含0。在乘积类题目里0的存在会让“除法思路”万劫不复这也正是238题禁掉除法的深层原因。处理0的唯一可靠方案就是老老实实做前缀积和后缀积的两遍扫描千万别在0上耍小聪明。第五种是k大于数组长度。轮转数组里k不取模直接翻转十次有九次结果不对。这属于“数学边界”问题凡是对下标做加减乘除、取模、移位操作的题目都要先想想操作数是否可能超出数组有效范围。5.2 超时与报错的两条排查路径遇到数组题报错先分清楚是RE还是TLE。RE是运行时错误通常是下标越界、空指针、访问了非法内存TLE才是算法复杂度问题。这两类问题的排查路径完全不同。我的排查步骤是四步走。第一步确认是哪种错误TLE直接去优化复杂度别在边界条件上浪费时间。第二步把过不了的用例缩小到长度5以内手工模拟一遍流程打印中间变量看看是不是哪一步的索引偏移带偏了数据。第三步针对题目本身跑极端用例空数组、全相等数组、含0数组、极大极小数组一口气全跑一遍而不是等测试用例把答案崩出来再去找。第四步重点检查所有“减一”操作前缀和里presum[i-1]在i0时的行为、窗口收缩时left和right的初始化是否覆盖了数组两端这些位置最容错出问题。我在写“和为K的子数组”时把seen[0]1写成了seen[0]0结果所有从数组起点开始的合法子数组全部漏掉。第一次提交WA后我没去检查初始化反而盯着循环逻辑看了十分钟最后才在一行注释里发现了问题。这种初始化错误在数组题里极其常见养成“先怀疑初始化再怀疑循环逻辑”的排查习惯能省下大量时间。6. 给Day13之后的话怎么把数组题练成条件反射在普通数组这个分类里挣扎了一整天之后我最大的体会是刷数组题不要背模板要记触发条件。看到求连续子数组的总和先问自己数组是否含负数决定用滑动窗口还是前缀和看到原地O(1)的约束先想翻转法、荷兰旗、摩尔投票这三件套能不能套上看到区间合并接受“排序扫描额外数组”这个标准答案不要为难自己去做原地压缩。我还给自己建了一个错题卡卡片上不写完整解法只写“识别特征犯过的错”。比如“560的坑seen[0]漏初始化、先登记再查询会把空子数组算进去”“189的坑k没取模”“75的坑遇到2交换后cur不能加1”。这张卡片在后续复习里比任何题解笔记都管用。最后再分享一个小技巧是我踩过很多次坑之后养成的习惯数组题WA的时候第一件事永远是打印数组长度、首尾元素、以及前缀和数组的前三个值和后三个值。大多数时候错误会在这个输出里立刻现出原形。Day13的绝境求生手册写到这儿真正的绝境其实不是题目本身而是你明明能AC却因为少处理一个边界在提交按钮上反复横跳时的那种心态崩坏。希望这份手册能让你少崩几次。