每次刷题看到“最大子数组和”“合并区间”“轮转数组”这三道题放在一起我都会有种很奇妙的感觉。它们看起来是三条完全不同的路线一个考你动态规划的基本功一个考你对排序后数据结构的敏感度一个考你对数组下标和翻转的理解。但真正把它们放在同一个刷题清单里反复研究之后我发现它们都在反复强调同一件事——数组问题看似解法众多顶层思路其实就那么几条关键在于你能不能根据数据特征快速选中正确的切入方式。这篇文章不适合完全零基础的同学直接硬啃但如果你已经能独立写出两层循环、并且有过几次“思路对但边界写崩”的经历那这三道题就是为你量身定制的进阶补强。我会把每一道题的暴力切入点、为什么它能优化、以及在线提交时最容易出问题的细节全部走一遍。这篇刷完你再看数组类问题会有种“骨架感”而不是一道题一道题地死记。1. 为什么把这三道题放在同一个刷题清单里先说结论三道题按难度梯度刚好踩中了数组算法里最常被考察的三个层次——连续子结构的约束、无序二维区间的归并、整体位移的重排。分别对应动态规划、排序贪心、原地变换。每个层次里都有一道变动后能衍生出一堆扩展题的代表题。很多刷题者的习惯是按“题号从前往后”或“随机点开一道”来刷这样容易导致在两个同质化题目上反复花时间而对于真正拉开差距的“为什么这步能这样做”缺乏深度思考。把这三道题放在同一天过一遍你会看到数组问题虽然题干差异很大但它们的优化路径高度相似先写暴力解看清楚时间花在哪个环节然后用“利用顺序关系”、“利用排序”、“利用模运算”把这部分计算省略掉。这里还需要说明一个匹配关系53题的关键词是“连续”隐含了必须保持原数组的先后次序56题的关键词是“区间”处理的是一组无序坐标189题的关键词是“右移”本质是数学上对下标做一个偏移映射。这三个词几乎覆盖了所有数组类题目的提问方式所以这套题单很适合用来做“数组专题总结日”。一次刷完比你断断续续刷十道不同题型要有效得多。2. 最大子数组和从暴力双层循环到一行递推这道题官方名字叫“最大子数组和”输入是整数数组要求找到一个连续子数组让它加和最大返回这个最大值。我第一次碰这道题时第一反应是那暴力枚举所有子数组不就完了没错理论上任何数组问题都可以用枚举解决。2.1 暴力解法先看清成本在哪里枚举所有子数组的标准写法是两层循环外层定起点内层定终点为了累加方便还可以顺手开一个前缀和数组把区间和从O(n)降到O(1)。即便加了前缀和优化枚举所有起点和终点的组合本身仍然是O(n²)——10万个元素的输入直接超时。暴力解真正的价值不在于能通过而在于帮你建立一个最朴素的语义“最大子数组和”说白了就是在所有区间 [i, j] 的和里取最大值。你的优化目标只有一个——能不能跳过大部分不必要的区间不损失正确性。2.2 为什么递推公式必须“以i结尾”来定义这是整道题最核心的认知拐点。很多教材会直接甩给你dp[i] max(dp[i-1] nums[i], nums[i])但没人跟你说清楚这个dp[i]到底是什么。如果你定义成“前i个元素里最大子数组的和”递推时你会发现一个问题前i个元素的最大子数组可能根本不以第i个元素结尾那算第i1个元素的时候你完全不知道该不该把它接上去。正确做法是让dp[i]表示以第i个元素结尾的子数组能取到的最大和。这样就强制每个子数组都有一个“尾部”计算下一个位置时只有两种选择把nums[i]接到前一个最优尾部后面或者干脆从前一个尾部断开、从nums[i]自己重新开始。这就是上式中max两个分支的含义。你可以把它理解成一条贪吃蛇新食物来了要么吞掉让尾巴延续要么甩掉旧尾巴从头开始每一步只看蛇尾处的状态不要贪恋前面一整条蛇的长度。写代码的时候还不需要真的开一个数组只需要一个变量记录“以当前元素结尾的最大和”另一个变量全局扫一遍取最大值即可空间从O(n)压缩到O(1)。def maxSubArray(self, nums: List[int]) - int: cur_sum nums[0] best_sum nums[0] for i in range(1, len(nums)): cur_sum max(nums[i], cur_sum nums[i]) best_sum max(best_sum, cur_sum) return best_sum这段代码有一个容易踩的坑cur_sum初始值不能写成0否则在数组全为负数的情况下你会得到0而不是最大的那个负数。很多人在这个细节上挂过一次负数数组恰恰是这道题最常见的边界数据。2.3 顺带说的分治解法为线段树铺路除了递推进阶这道题还存在一种分治做法把数组从中间劈开最大子数组要么完全在左半要么完全在右半要么横跨中点。横跨的情况必须从中间向两边扩展扫描取最大。每一层归并统计复杂度O(n log n)。分治解法单独看不如递推优秀但它衍生出的一个四元组表示法是后面线段树题目里维护区间最大子段和的基础。你如果在学线段树会发现每个树节点要存四个值区间总和、最大前缀和、最大后缀和、最大子段和。这四者之间正好存在和递推公式同构的合并关系。所以这道题别只背递推把它当“最小区间查询模型”去理解后面的题会顺畅很多。3. 合并区间排序解决“谁跟谁重叠”的本质难题56题给的是一堆形如 [start, end] 的区间要求把有重叠的部分合并最后输出不重叠的完整集合。这题我习惯先用一个具体场景来进入状态想象你有几段日志分别记录了不同时段的CPU占用率时间线有交叠现在要输出最终每个区间的起止时间。区间没有排序如果两两比较谁跟谁有交集那是一个典型的O(n²)嵌套扫描。3.1 排序之后“区间重叠”从二维比较降成一维扫描这里的核心洞察是重叠关系虽然发生在两个端点上但是当你按每个区间的start升序排好之后原来那个“任意两个区间都可能发生关系”的问题就变成了“新来的区间只需要和当前已合并区间末尾比较”的问题。因为start已经有序所以新来的区间不可能和更早的某个已合并区间发生交集却和当前合并区间无关——如果它跨越了那个更早区间它一定也跨越了排在中间的所有区间。排序后整个合并过程就是一趟线性扫描维护一个cur区间遇到新区间先看它的start是否落在cur的范围内是则把cur.end更新为两者end的较大值否则说明cur已经不可能再被后续区间延伸把它收进结果列表开始一个新的cur。def merge(self, intervals: List[List[int]]) - List[List[int]]: intervals.sort(keylambda 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 merged3.2 更新右端点时最容易写错的一行网上很多版本的合并代码里最容易写错的地方就是把merged[-1][1] max(...)直接写成merged[-1][1] interval[1]。表面看新来的区间end一定比当前的大因为start都已经有序了可end是乱序的。比如你先合并出[1, 10]接着来了一个[2, 6]如果直接用6覆盖10那这个合并区间就凭空缩水了。正确写法必须取历史end和当前end的较大值否则数据一复杂就会漏掉后半段的重叠区域。另一个小问题是用while还是for。这个场景每轮要么“延长cur”要么“收cur开新cur”不存在需要回头处理多个区间的场景所以一层for就够了。如果写成while去反复比对当前结果列表最后一个区间会绕进死循环里也没必要。3.3 边界比较到底用“”还是“”判断两个区间是否重叠很多人纠结用还是。看题目描述里的措辞如果明确说明区间相接也算合并那就要用像这道题LeetCode的描述里实际处理时相接的情况按合并处理。判断是否重叠的标准新区间的start大于cur.end那肯定不重叠。否则就说明存在交集或相接应该合并。这一段我建议你去题目的讨论区看看不同写法下的用例差异自己动手改一下运算符跑几个用例比谁告诉你结论都管用。4. 轮转数组三次翻转背后的原地转置思维189题是给一个数组向右轮转k位比如[1,2,3,4,5,6,7]向右转3位会变成[5,6,7,1,2,3,4]。这题最容易的解法不是任何技巧而是开辟一个新数组按映射关系填回去新位置等于原位置加k再对长度取模。这个解法时间复杂度O(n)空间复杂度O(n)完全能过题只是面试时多半会被追问一句“能不能在原数组上完成”。这一问就把题目从“考你模运算”拉高到“考你原地重排的能力”。4.1 环状替换看似直接但步数很难算对原地旋转的第一直觉是跟着元素走从下标0开始把nums[0]存到临时变量把它该去的位置nums[k % n]覆盖前先备份再继续往下跳。这个思路成立但你很快会发现一个问题跳了一圈回到起点时有可能还有一批元素没碰到。比如n6k4你从0出发跳4步到4再到2再到0只经过3个位置剩下3个没被移动。决定从几个起点出发的数学依据是gcd(n, k)。n和k的最大公约数是多少就有多少个独立环。代码里需要外层循环控制起点从0到gcd-1内层while一直跳到回到起点为止。这个实现虽然空间O(1)但是写起来的边界和取模逻辑很容易绕进去。我在面试现场写过一次翻车率极高多数人不是思路不对而是环与环之间切换的起点位置算错。4.2 三次翻转为什么是最优雅的原地解法环状替换复杂可要是换个角度看这个问题向右轮转k位本质上是把数组分成了后半段k%n个元素和前半段n-k%n个元素然后把这两段整体交换位置。想原地交换两整段办法很简单——先分别反转每一段再把整个数组反转一次。举刚才那个例子原数组[1,2,3,4,5,6,7]k3先把整个数组反转成[7,6,5,4,3,2,1]再反转前三个变成[5,6,7]接着反转后四个变成[1,2,3,4]拼起来就是[5,6,7,1,2,3,4]。看起来像魔法数学上不过是用两次reverse抵消了一次reverse而已。def rotate(self, nums: List[int], k: int) - None: n len(nums) k % n nums.reverse() nums[:k] reversed(nums[:k]) nums[k:] reversed(nums[k:])实现时最容易忽略的是开头那个k % n。k比n大的情况在测试用例里非常常见输入[1,2]、k3如果直接翻转到倒数第三位Python的负索引逻辑会让你得到完全错误的结果。先把k对n取模后面所有操作都在轮回内逻辑瞬间清晰。还有一点这里的切片赋值写法依赖Python的切片机制如果换到别的语言你需要手写一个reverse辅助函数并且注意reverse的区间是左闭右开还是左闭右闭这是跨语言最容易踩的坑。4.3 你其实不需要每次都写原地版本如果是工程代码里真的需要轮转数组Python里直接用切片拼接一行就能搞定nums[:] nums[-k:] nums[:-k]。这个写法空间复杂度是O(n)的因为切片会创建新列表但它的可读性远高于三次翻转。做题现场我建议你优先把这种简单写法写完、验证边界再在脑内推演三次翻转的版本去应对追问。不要一上来憋着写最优解写崩了反而连基础分都没了。5. 刷完三道题之后真正要留意的五处边界细节这三道题单独刷可能各自都能过但放在一起你会发现大量时间其实不是花在算法思路上而是花在边界条件的试错上。我把反复踩过的几个坑统一列出来省得你在同一处浪费两次提交机会。5.1 括号开闭区间统一中间变量别混用53题用cur_sum递推56题用merged[-1][1]代表当前合并区间右边界189题用k % n消除轮回冗余。这三个细节背后全是“中间变量的语义一致性”问题。写代码时每个变量在循环体执行前是什么含义执行后必须更新成什么含义都要在注释里写清楚。我见过有人把cur_sum和best_sum弄混到后半段才想起来cur_sum不是全局最大也见过56题把cur.end更新后下一轮又拿旧cur.end去比较新区间。5.2 全负数、空数组、单元素数组这三类用例永远先跑全负数53题如果不注意初始值会输出0而不是负数。空数组56题的输入如果为空你要确认自己的代码不会访问merged[-1]导致下标越界虽然LeetCode的测试集一般不会给空输入但自己写的工具函数很可能遇到。单元素数组189题的k取模后为0整个数组不需要任何翻转如果你的代码不管三七二十一先做了reverse就会把唯一元素原样翻一遍——这没问题但配合切片边界时可能产生空切片需要留意是否影响结果。这三个用例是我每次提交前必跑的“安全三件套”跑完它们大部分边界问题会提前暴露。5.3 原地修改和返回值要分清189题是原地修改nums函数不返回新数组而56题需要返回一个新的合并结果列表原数组可以不动53题则只返回一个整数连数组修改都不涉及。LeetCode的本地测试对这三者一视同仁但如果你把代码搬到自己封装的工具函数里很可能会因为“到底要不要改原数组”产生困惑。建议在执行函数前先读清楚注释里是“in-place”还是“return new”养成习惯。5.4 排序的稳定性在这些题里重要吗56题里对区间排序只按start排对于start相同的区间顺序无所谓因为无论谁排在前面扫描时最终都会落到同一个合并区间里所以稳定性在这里不重要。但如果你在扩展题里需要额外记录区间原始位置之类的信息就必须留意sort函数默认的稳定性。这个细节不刷到这里很容易忽略一碰到需要“保留原相对顺序”的变形题你会被坑一道题的提交时间。5.5 做题时的顺序感先暴力验证再优化表述我自己刷这套题单时的顺序是先不关心中间变量三题各写一个暴力/朴素版本把样例跑通然后再逐题优化。这样做的最大好处是暴力版本能帮你验证优化版本的结果对不对万一优化版本写错了你可以用注释掉的暴力代码做对照调试直接上优化版本出现错误时你很难判断到底是思路错了还是边界写错了。这一套“先笨后巧”的顺序在面试白板题上同样适用面试官更看重你能不能用最朴素的方式先明确问题定义再逐步收敛复杂度。功能层面这套题单已经覆盖得很全动态规划、排序贪心、翻转重排全是高频考点。但我更想强调的是刷完它们之后你对数组问题的理解会从“看到题目想模板”变成“先判断这题考的是顺序选择、区间关系、还是下标映射”。这种判断力才是这三道题放在一起的真正价值。我之后遇到类似“合并时间段”或“旋转矩阵”的题目时都会不自觉地回忆起这次归纳——它们的核心还是这三板斧在变着花样考你。