每次刷题看到“最大子数组和”“合并区间”“轮转数组”这三道题放在一起，我都会有种很奇妙的感觉。它们看起来是三条完全不同的路线：一个考你动态规划的基本功，一个考你对排序后数据结构的敏感度，一个考你对数组下标和翻转的理解。但真正把它们放在同一个刷题清单里反复研究之后，我发现它们都在反复强调同一件事——数组问题看似解法众多，顶层思路其实就那么几条，关键在于你能不能根据数据特征快速选中正确的切入方式。
这篇文章不适合完全零基础的同学直接硬啃，但如果你已经能独立写出两层循环、并且有过几次“思路对但边界写崩”的经历，那这三道题就是为你量身定制的进阶补强。我会把每一道题的暴力切入点、为什么它能优化、以及在线提交时最容易出问题的细节全部走一遍。这篇刷完，你再看数组类问题会有种“骨架感”，而不是一道题一道题地死记。
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个元素结尾，那算第i+1个元素的时候，你完全不知道该不该把它接上去。
正确做法是让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(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 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]覆盖前先备份，再继续往下跳。这个思路成立，但你很快会发现一个问题：跳了一圈回到起点时，有可能还有一批元素没碰到。比如n=6，k=4，你从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]，k=3，先把整个数组反转成[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]、k=3，如果直接翻转到倒数第三位，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 做题时的顺序感：先暴力验证，再优化表述
我自己刷这套题单时的顺序是：先不关心中间变量，三题各写一个暴力/朴素版本把样例跑通；然后再逐题优化。这样做的最大好处是，暴力版本能帮你验证优化版本的结果对不对，万一优化版本写错了，你可以用注释掉的暴力代码做对照调试；直接上优化版本出现错误时，你很难判断到底是思路错了还是边界写错了。这一套“先笨后巧”的顺序在面试白板题上同样适用，面试官更看重你能不能用最朴素的方式先明确问题定义，再逐步收敛复杂度。
功能层面这套题单已经覆盖得很全：动态规划、排序贪心、翻转重排，全是高频考点。但我更想强调的是，刷完它们之后，你对数组问题的理解会从“看到题目想模板”变成“先判断这题考的是顺序选择、区间关系、还是下标映射”。这种判断力才是这三道题放在一起的真正价值。我之后遇到类似“合并时间段”或“旋转矩阵”的题目时，都会不自觉地回忆起这次归纳——它们的核心，还是这三板斧在变着花样考你。
