1. 写在前面Day2到底在练什么代码随想录Day2不少跟着刷题的朋友都有体会这一天是数组专题的第二天题目数量不多但信息量其实很大。Day1讲二分法和移除元素解决的核心问题是“在有序数组里怎么高效查找”和“怎么在原地删掉指定值”而Day2这三道题——有序数组的平方、长度最小的子数组、螺旋矩阵II——恰好把数组处理中最容易踩坑的三个场景全覆盖了双指针、滑动窗口、矩阵模拟遍历。如果你以为数组题就是for循环套for循环那做完这一天的题心态大概率会被矫正一次。这天最值得沉淀的东西不是某道题的答案而是三条能迁移的思维主线。第一数组的“有序性”一旦被打破比如平方之后负数变正数原来的单调性会怎么变化双指针怎么抓住新规律。第二连续子数组求和类问题时暴力解和滑动窗口解的差别到底在哪里什么时候应该移动左边界。第三矩阵模拟填充的本质其实是把“循环不变量”讲清楚——每一条边走到什么位置边界谁来守稍有不慎就会写出越界或者死循环的代码。这篇内容适合两类人看一类是按代码随想录刷题打卡、刚好做到Day2的同学可以直接对照思路和代码另一类是已经刷过一遍、觉得“题看懂了但写不出来”或者“写出来但老差一点”的人我会把易错细节和排查方法都展开讲帮你把这三道题彻底吃透而不是背过。2. 整体设计与思路拆解2.1 为什么是三题一组的编排逻辑Day2三道题并不是随便凑的。从题目名称看它们属于数组这个大类但考察的知识点却代表了数组算法题的三种典型形态。有序数组的平方本质是“在一个已知有序的数组上做变形运算并回到有序状态”。它要求你先发现平方后序列的单调性规律再决定用什么策略排序。长度最小的子数组本质是“连续子数组的区间搜索”。它考察的是对于“滑动窗口”形态的敏感度什么时候该扩张、什么时候该收缩、什么时候该记录答案。螺旋矩阵II本质是“按规则遍历二维数组并写入值”。它不考复杂的数学结构考的是对边界的拆解能力和对循环不变量的贯彻能力。这三道题组合在一起正好覆盖了数组题中最容易翻车的三个地方规律不容易一眼看穿平方后的双指针、暴力能做但复杂度超标子数组求和、看似简单但写起来处处是坑螺旋遍历。跟着这个序列走一遍等于给算法基本功做了一次系统性的查漏补缺。我在实际带朋友刷题的时候发现很多人Day1的二分法和移除元素掌握得还不错一到Day2就明显变慢原因往往是Day1的题目即便用了双指针指针的移动逻辑比较直白Day2的题目需要先证明“为什么可以这么做”再动手写代码。缺少这一层证明的同学写出来的代码往往能过用例但换一个输入规模或者边界条件就崩。所以这一天的核心不是记代码而是补上“我在动手之前到底想清楚了没有”这个习惯。2.2 三条主线背后的底层共性如果从更高一层去看这三道题会发现它们都离不开一个词数组的索引关系。数组在内存中是连续存储的这决定了它有两个特点一是可以通过下标O(1)访问二是“子区间”这个概念可以用两个下标来维护。双指针、滑动窗口、矩阵行遍历本质上都是在管理一组下标。区别只在于双指针关注的是两个端点上的值滑动窗口关注的是两个端点之间的和或长度螺旋遍历关注的是二维坐标的变化方向。理解了这一点再看Day2的题目就不会觉得它们彼此割裂。你把“有序数组的平方”中的左右指针看作窗口的两个边界其实也能从“窗口内元素按某个规则重新排列”的角度去理解你把“长度最小的子数组”中的滑动窗口看作在数轴上不断伸缩的区间本质上和二分查找里维护的区间也有相通之处。代码随想录这个系列一直强调“方法论”原因就在这里一味堆题量不如把一个方法在不同场景下用熟遇到新题才有迁移的基础。2.3 这一天需要的预备知识按照代码随想录的刷题路线Day1的内容默认你已经掌握了。除此之外Day2还需要你在动手前确认自己清楚三件事。第一时间复杂度分析的基本方法。至少能判断O(n)、O(n log n)、O(n^2)之间的差异否则很难理解为什么滑动窗口比暴力枚举好。第二二维数组的坐标表示。螺旋矩阵II看起来复杂但如果对Matrix的行列坐标足够敏感理解代码会轻松很多。第三循环不变量的思维习惯。这个我在后面会反复提到。简单说写循环前先确定“每一步里哪些位置是确定的、哪些是待处理的”循环里始终守住这个约定。如果你这三项还有薄弱的地方不要急着开始做题先花半小时把底子补一补。磨刀不误砍柴工这句话在刷算法题这里特别适用。3. 有序数组的平方双指针的正确打开方式3.1 题目与暴力解分析题目是LeetCode 977给定一个按非递减顺序排序的整数数组nums要求返回每个数字的平方组成的新数组同样按非递减顺序排序。最直觉的思路是先算平方再整体排序。比如nums [-4, -1, 0, 3, 10]先得到[16, 1, 0, 9, 100]然后排序得到[0, 1, 9, 16, 100]。这个解法的时间复杂度是O(n log n)主要消耗在排序上。如果面试时你先说出这个解法面试官通常会追问一句能不能优化到O(n)。优化的切入点其实藏在一个很容易忽略的细节里原数组已经有序。平方只是对每个元素做单调变换但负数平方后大小关系会反转比如-4的平方是16大于3的平方9。于是数组在平方后呈现出“中间小、两边大”的形态。最大值一定出现在两端要么是第一个元素平方要么是最后一个元素平方这给了双指针一个非常舒适的使用场景。3.2 双指针思路的推导过程既然最大值在两端最自然的做法就是用两个指针分别指向数组的两端比较它们所指向元素的平方大小把更大的那个放到结果数组的最后一位然后移动对应的指针。重复这个过程直到两个指针相遇。这里有一个新手容易犯迷糊的问题为什么结果数组要从后往前填而不是从前往后填原因是我们每次找出来的是当前剩余元素中最大的那个如果从前往后填结果数组的性质是“从头开始越来越小”这显然不对。从后往前填天然地让最大的元素先占据最后的位置剩下的依次向前填正好得到递增序列。我当初第一次写这道题的时候也尝试过“从中间向两边走”的思路——先找到绝对值最小的位置然后左右扩散。听起来很合理但实现起来要先寻找这个中间位置多了一步复杂度为O(n)的查找而且中间位置可能存在多个比如负数到非负数交替时代码容易写成一团乱麻。相比之下双指针从两端向中间收缩完全不需要定位中间点简洁且不容易出错。这个对比让我后来在做题时养成了一个习惯如果一个算法需要额外步骤才能确定起点通常还有更自然的解法。3.3 关键代码与细节注释以Python为例一个清晰的双指针写法如下def sortedSquares(nums): n len(nums) res [0] * n left, right 0, n - 1 pos n - 1 while left right: left_sq nums[left] ** 2 right_sq nums[right] ** 2 if left_sq right_sq: res[pos] left_sq left 1 else: res[pos] right_sq right - 1 pos - 1 return res几个细节值得展开讲。循环条件是left right而不是left right。如果漏掉等号当left和right指向同一个元素时这个元素会被跳过。数组长度为奇数时中间那个元素是绝对会被漏掉的结果会少一个数。比较平方大小的时候不需要提前把每个元素都平方放到新数组直接在原数组上取值计算平方即可省一次遍历也减少一块额外内存。这里的空间复杂度是O(n)结果数组本身要占空间代码里没有再开辟别的数组已经是较优解。当left_sq等于right_sq时走else分支取右侧的数字其实不影响结果你也可以取左侧。但要注意不能让两个分支都漏掉元素left和right的更新必须放在各自分支里且每次循环只移动一个指针。3.4 螺旋式进阶从这道题提炼的双指针原则很多刷题指南总结双指针的时候会分成“快慢指针”“左右对撞指针”“滑动窗口”等类别。有序数组的平方是左右对撞指针的典型案例。它的本质是利用数据本身的单调性在一次遍历内完成原本需要排序才能完成的工作。把这个原则记住当数组本身有序但经过某种变换后局部单调性反转考虑两端取值两个指针向中间逼近往往能得到O(n)的解法。这个思路在后面很多题目里都会复用比如面试里常常出现的“两数之和II - 输入有序数组”也是同一套对撞指针逻辑。我推荐大家在本地写完这道题后专门测试三个用例全是负数的数组、全是非负数的数组、只有一个元素的数组。这三种情况能帮你确认循环边界和结果数组索引没有问题。别嫌测试用例简单很多边界bug正是在这些“一分钟用例”里暴露出来的。4. 长度最小的子数组滑动窗口为什么是O(n)4.1 题目解读与暴力解的上限题目是LeetCode 209给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和大于等于target的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回0。我刚开始做这道题时脑子里浮现的方案很直接枚举所有可能的连续子数组计算每一个的和记录满足条件的最小长度。这样做确实能解但时间复杂度是O(n^2)。还可以用前缀和优化把“计算子数组和”变成O(1)的查表再配合二分查找能把复杂度压到O(n log n)。但这不是最优解面试官大概率还会继续追问。为什么要追求O(n)因为题目里的“连续子数组”和“长度最小”这两个条件天然适合用一个伸缩的窗口来维护。窗口里的元素和就是我们关心的状态窗口两端就是两个指针窗口的伸缩过程保证了每个元素最多被加入一次、移出一次总操作次数是线性的。4.2 滑动窗口的收缩逻辑滑动窗口的思路是用右指针向右扩展窗口把新元素纳入窗口和当窗口和大于等于target时记录当前窗口长度然后尝试移动左指针缩小窗口看能否在不破坏“和大于等于target”的前提下得到更短的子数组。这里有一个困扰很多人的问题为什么右指针只往前走不需要往回退因为我们要找的是最短子数组一旦右指针到达某个位置后窗口和已经满足条件再向右扩展只会让窗口更长不可能得到更优解所以此时应该收缩左边界而不是继续扩展右边界。每一次右指针的移动都对应一个“以当前右端点为终点的最短可行窗口”的尝试而左指针的收缩则是尽最大努力缩短这个窗口。两个指针的移动方向都是单调的因此整体是O(n)。你可以类比成两个人拉一条尺子右端持续往外拉拉到绳子绷紧满足条件了就记录一格长度然后左端往里收收到绳子不紧为止再继续拉右端。整个过程每个人都只往一个方向移动总共也就走完整个尺子长度不会回头。4.3 代码实现与易错点Python实现如下def minSubArrayLen(target, nums): left 0 window_sum 0 min_len float(inf) for right in range(len(nums)): window_sum nums[right] while window_sum target: min_len min(min_len, right - left 1) window_sum - nums[left] left 1 return 0 if min_len float(inf) else min_len这里的核心是while而不是if。当窗口和大于等于target时可能连续收缩多次才能重新低于target比如窗口里全是很大的数收缩一次后和仍然大于等于target这时需要继续收缩。如果写成if只收缩一次就走人会漏掉更短的答案。窗口收缩的顺序也容易出错。要先更新min_len再减掉左边元素。很多新手会先把nums[left]减掉再更新长度这时候left已经指向下一个位置窗口长度就不对了。做题时我习惯先在纸上标注出“记录答案的时刻”和“改变状态的时刻”分清楚顺序再写代码。返回0的情况也很重要。如果整个数组遍历完窗口和始终没达到target此时min_len仍然是无穷大要返回0。这个分支在示例用例里不一定触发但真实测试数据里一定会出现。别偷懒省略它。4.4 滑动窗口的活用边界做完这道题不妨再想一个变体如果数组里存在负数滑动窗口这个解法还成立吗答案是大概率不成立。因为窗口左端收缩时加入负数可能让窗口和下降但右指针继续扩展时也可能因为一个负数让已经满足条件的窗口重新不满足。这就破坏了“窗口和随右指针单调不减”的前提滑动窗口的复杂度分析也随之失效。这个点是我实际面试中遇到过的追问方向。面试官问得不深但如果你能主动说出“这个解法依赖数组全为正数”这个前提印象分会好很多。这也是为什么我一直建议大家在做题后多想一步尝试改变一个条件看老方案还灵不灵这样能帮助你在脑子里建立一个“解法适用条件”的清单。5. 螺旋矩阵II循环不变量的实战演练5.1 为什么这道题让人头大题目是LeetCode 59给定一个正整数n生成一个包含1到n^2所有元素、且元素按顺时针顺序螺旋排列的正方形矩阵。这道题的难度不在于算法思想而在于实现过程中对边界的控制。很多人第一次写的时候会下意识地把四条边分别用四个for循环填完然后在while循环里重复。但问题来了每一条边走到哪里算结束如果每条边都走到角落那拐角处的元素会被重复赋值最后生成的矩阵面目全非。代码随想录里反复强调“循环不变量”螺旋矩阵II就是检验你懂没懂这个概念的最好题目。所谓循环不变量简单说就是在循环里始终遵守同一个边界约定。比如你规定每一条边都遵循“左闭右开”的填充原则即每一条边只填充到该边的倒数第二个位置那么一圈下来四个角正好被下一条边接管不会出现重叠。如果这次填充到末尾下次又从同一个位置开始就是边界混乱的根源。5.2 左闭右开的填充策略假设我们按照“左闭右开”来填充每条边都从起点开始填充到终点前一个位置就停下。以n4为例第一圈的填充过程如下上边从左到右填充第0行的第0列到第2列剩下列3交给右边。右边从上到下填充第3行的第0列到第2列这里的“第0列”指从第1行开始的三个位置剩下行3交给下边。下边从右到左填充第3行的第3列到第1列剩下列0交给左边。左边从下到上填充第2行的第0列到第1行剩下行0是已经填过的位置。走完这一圈外圈被完整填充。每完成一圈就把起始位置沿对角线往里缩一格同时控制“终点”的偏移量加一。当n是奇数时循环到最后只剩一个中心位置需要单独处理。这种策略的好处是每次填充的范围在当前圈内是固定的圈与圈之间通过一个offset偏移量控制不会出现不同圈的边界互相干扰的问题。5.3 代码实现与偏移量剖析def generateMatrix(n): matrix [[0] * n for _ in range(n)] top, bottom, left, right 0, n - 1, 0, n - 1 num 1 while top bottom and left right: for i in range(left, right 1): matrix[top][i] num num 1 top 1 for i in range(top, bottom 1): matrix[i][right] num num 1 right - 1 if top bottom: for i in range(right, left - 1, -1): matrix[bottom][i] num num 1 bottom - 1 if left right: for i in range(bottom, top - 1, -1): matrix[i][left] num num 1 left 1 return matrix这个写法用的是“四条边分别填充、填完收缩边界”的思路。跟“左闭右开循环”略有不同这里每个方向都填充到当前边界的最末端但通过及时移动边界确保同一位置的元素不会被二次填充。两种思路都能正确地完成任务关键是你得严格坚持其中一种不要混合。四个for循环里后两个必须加if判断。原因在于当矩阵只剩一行或一列时上边的填充已经完成了该行下边这一个循环就不该再执行只剩一列时右边的填充已经完成了该列左边的循环就不该再执行。如果缺少这两个判断即使矩阵是正方形在处理到最内层时也很容易产生重复赋值。后面两个for循环的range起始值要特别注意。填下边时起点是right终点是left方向是从右往左所以步长是-1填左边时起点是bottom终点是top方向是从下往上步长同样是-1。这个方向的判断我建议在写代码前先在草稿纸上画一个小矩阵把每个循环要填充的格子点出来再动手写能省去大量调试时间。5.4 从螺旋矩阵提炼的经验螺旋矩阵这道题我见过不少朋友在“为什么最后要单独处理中心位置”这个问题上卡壳。其实答案很简单如果n是奇数螺旋填充到最后一圈时矩阵只剩一个中心位置此时四条边的起始边界都指向同一个位置如果继续用for循环填四条边就会重复赋值。单独处理中心点或者事先在主循环里判断“是否只剩下一个元素”是两种常见的解决方案。这道题另一个值得留意的点是二维数组的行列对应关系。matrix[row][col]中第一个索引是行第二个索引是列。填充上边时行固定、列变化填充右边时列固定、行变化。搞反这两个维度的顺序是新手写这道题最常犯的错误之一而且这种错误不容易一眼看出来因为小规模用例可能碰巧通过。我建议你在自测时打印每一步填充后的矩阵逐圈检查很快就能定位是哪里写反了。6. 常见问题与排查技巧实录6.1 这三道题的高频错误对照表我把这段时间帮朋友看代码时最常出现的问题整理了一下做成一个速查表。你可以按图索骥对照自己写的代码快速排查。题目典型错误表现排查方向有序数组的平方循环条件写成left right奇数长度数组少一个元素改为left right有序数组的平方结果数组从前往后填结果顺序是递减的让pos从n-1开始递减赋值长度最小的子数组用if替代while收缩窗口部分用例返回的长度偏大改为while window_sum target长度最小的子数组先收缩left再记录min_len返回长度比实际小1先记录长度再移动left螺旋矩阵II四条边都无脑执行最内层元素重复赋值后两个循环加if边界判断螺旋矩阵II行列坐标写反矩阵形状不对称、值错乱在纸上标出row和col变化方向这个表格列出来的每一项我都在真实代码里见到过而且往往不是单一的bug而是两三个叠加在一起。建议你遇到报错时先判断错误属于“越界”“缺少元素”还是“重复赋值”再针对性地去检查对应位置效率会高很多。6.2 一个印象深刻的调试过程有一次帮朋友调长度最小的子数组他写的代码在本地测试了好几个随机数组都能通过但提交到OJ上就有一个用例输出比预期大1。我一行一行看过去最后发现他在窗口收缩时写的是window_sum - nums[left] min_len min(min_len, right - left 1) left 1问题出在顺序上。他先减掉了窗口最左边的值再用right - left 1计算长度但由于left此时还没更新窗口长度算出来的其实是“去掉左边元素之前的原窗口长度”而窗口和已经是收缩后的状态两者不匹配。虽然在某些用例里碰巧不影响答案但在极端情况下就会差1。把min_len的更新挪到left自增之前问题就解决了。这类顺序问题往往是最隐蔽的bug。代码逻辑看起来每一步都对但“先记录还是先改变”的时机错了结果就差那么一点。我的经验是凡是涉及“基于旧状态做判断、然后更新状态”的场景先问自己一个问题旧状态是什么时候失效的答案必须在状态更新前被消费完。6.3 自测用例的设计思路刷题时很多人习惯做一道题就提交然后看OJ给不给过。但对于Day2这类代码量不大但边界细节很多的题目我更推荐先准备好几组本地用例跑完再提交。这样能省下反复提交的时间也能培养对边界的敏感度。有序数组的平方nums [-5, -3, 2, 4]nums [0, 0, 0]nums [1, 2, 3]长度最小的子数组target 15, nums [1, 2, 3, 4, 5]target 4, nums [1, 1, 1, 1]target 100, nums [1, 2, 3]螺旋矩阵IIn 1n 2n 3n 4这些用例覆盖了“长度奇偶”“全正全负”“不存在答案”“最小规模”等情况。我建议你把这些用例保存成一个本地测试脚本以后刷题也能复用这个思路每一种边界类型都准备一个最小复现用例。7. 第二天复盘从会写到会讲刷完Day2这三道题我建议大家做一次复盘而不只是“跟着题解抄一遍”。复盘我一般分成三个步骤。第一步把每道题的思路用自己的话复述一遍。比如有序数组的平方你能不能在一分钟之内讲清楚“为什么最大值在两端、为什么结果数组从后往前放”。如果讲不清楚说明思路还没有完全内化。第二步把这三道题和之前做过的题建立联系。Day1的移除元素用到双指针Day2的有序数组平方也用到双指针但两个双指针的移动逻辑有什么不同Day1的左右指针不常同时移动Day2的左右指针每次只动一边。这种对比做多了你对算法模式的识别能力会明显提升。第三步想一想如果限制条件变了解法会不会失效。我在前面已经提到了负数对滑动窗口的影响。类似地如果有序数组的平方改成“立方并排序”双指针还灵不灵如果螺旋矩阵II改成“逆时针旋转”填充顺序要怎么调整这些假设都是很好的训练素材。代码随想录这套刷题路线的价值我个人的理解是它不追求用数量冲击你的记忆而是用精心挑选的题目帮你把每个专题的方法论打磨扎实。Day2作为数组中段的关卡无论你Day1学得怎么样都值得多花一点时间把这三道题彻底吃透。毕竟数组是很多算法题的骨架双指针和滑动窗口又是算法面试的高频考点这一段的基础打得牢后面遇到链表、字符串、哈希表里的双指针问题你都能更快地迁移思路。