题目描述
思路解析
一句话答案：LeetCode 1031 两个无重叠子数组的最大和：前缀和让定长窗口和一减就得，再扫两趟分别处理短段在前、长段在前，每趟边扫边维护左侧最优前段，时间 O(n)、空间 O(n)。
两个无重叠子数组的最大和在挑什么
给一个整数数组 nums 和两个长度 firstLen、secondLen，要找两段连续、互不重叠的子数组（子数组就是数组里挨着的一截），长度分别是这两个值，让两段元素和最大。题面 nums=[6,7,1,9,2,3,1]、firstLen=1、secondLen=2，答案 22。长度 firstLen 的段既能在另一段左边，也能在右边。
为什么逐对枚举两段位置会慢到跑不动
两段各自的起点都有大约 n 个，两两配对再查重叠就是 n² 量级，每对还要现算两段和，整体奔着 O(n³)（大 O 记号描述规模变大时操作数怎么涨）去，n 一大就跑不动。慢在重复：同一段的和被反复从头累加，同一种前后配置被换着枚举多遍。
前缀和凭什么让定长窗口和一减就得
最好省的是「反复算一段的和」。先建前缀和数组 s（前缀和就是从头累加到每个位置的总和）：s[0]=0 当哨兵、代表前 0 个数的和，s[k] 就是前 k 个数的总和。有了它，第 l 到 r 这段和就是 s[r+1]-s[l]，一次减法 O(1) 拿到。框住第 0 到第 1 格，和是 s[2]-s[0]=13-0=13，正好是 6 加 7。
一段固定另一段取左侧最优，两种顺序为何都要扫
配对不漏。先钉死一种顺序：长度 firstLen 的段在 secondLen 段左边。从左往右滑右段，滑到每处，左边可放的 firstLen 段里只有和最大的才可能最优——用滚动变量 t（一路扫、只记左侧至今最大的段和）盯住。右段每滑一步，先把新空出、能当左段的位置并入 t 取最大，再用 t 加当前右段和刷新答案，一趟就覆盖了「firstLen 段在前」的所有配对。
但 firstLen 段也可能在后。角色对调再扫第二趟：secondLen 段在左、t 改记左侧最优的 secondLen 段和，firstLen 段在右滑。两趟共用 ans 取最大，两种顺序就都兜住。
拿题面数组把两趟扫描亲手走一遍
先滚出 s=[0,6,13,14,23,25,28,29]。第一趟 firstLen=1 段在前、secondLen=2 段右滑：[7,1] 和 8、t=6 合 14；[1,9] 和 10、t=7 合 17；[9,2] 和 11、t=7 合 18；[2,3] 时 t 升到 9 但只合 14；[3,1] 合 13——第一趟最好 18。第二趟对调：右段到 [9] 时左侧最优的长度 2 段是 [6,7]、t=13 合 22，其余都不过 22。取大得 22，来自第二趟——长度 2 段 [6,7] 反在前。
只扫一趟为什么会把答案 22 算成 18
只扫第一趟就返回会把答案定在 18：那趟默认长度 1 的段永远在前，可最优解偏是长度 2 的 [6,7] 在前、长度 1 的 [9] 在后，得第二趟才扫到。复杂度上，前缀和一遍、两趟各扫一遍都是线性，时间 O(n)；额外空间主要是那条长度 n+1 的前缀和数组，空间 O(n)。两个边界：每趟开头必须把 t 清零，否则第二趟会把上一趟的旧最优错当本趟左段；两段长度之和等于数组长度时，答案就是整个数组的和。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
把整套思路压成两句:前缀和让窗口和「一减就得」；扫的时候一个窗口固定、另一个取左侧历史最优 t。两种前后顺序都要扫一趟。下面每帧都在套它。
先建前缀和 s，从一个哨兵 s0 = 0 开始，它代表「前 0 个数的和」。有了这个起点，后面每个 s 都能在上一个的基础上加一个数得到。
把第 0 个数 6 累进来:s1 等于上一项 s0 的 0 再加 6，得 6。前缀和就是这样一路滚出来的。
把第 1 个数 7 累进来:s2 等于上一项 s1 的 6 再加 7，得 13。前缀和就是这样一路滚出来的。
把第 2 个数 1 累进来:s3 等于上一项 s2 的 13 再加 1，得 14。前缀和就是这样一路滚出来的。
把第 3 个数 9 累进来:s4 等于上一项 s3 的 14 再加 9，得 23。前缀和就是这样一路滚出来的。
把第 4 个数 2 累进来:s5 等于上一项 s4 的 23 再加 2，得 25。前缀和就是这样一路滚出来的。
把第 5 个数 3 累进来:s6 等于上一项 s5 的 25 再加 3，得 28。前缀和就是这样一路滚出来的。
把第 6 个数 1 累进来:s7 等于上一项 s6 的 28 再加 1，得 29。前缀和就是这样一路滚出来的。
验证一下这个减法:框住第 0 到第 1 格这段，它的和就是 s2 减 s0，等于 13 减 0，正好 13，也就是 6 加 7。以后任何定长窗口和都这么一减得到，O(1)。
先扫第一趟，约定:长度 1 的窗口落在长度 2 的窗口「前面」。我们让第二个窗口从左往右扫，第一个窗口就在它左边取历史最优，用滚动变量 t 记着。t 和这一趟的答案 ansA 都从 0 起。
第二窗滑到 [1,2]，这两个数的和是 8。它左边能放的最好第一窗(绿色)和是 t = 6，两段相加 14。比之前更大，ansA 刷新成 14。（这一步顺手把第一窗最优 t 更新到了 6。）
第二窗滑到 [2,3]，这两个数的和是 10。它左边能放的最好第一窗(绿色)和是 t = 7，两段相加 17。比之前更大，ansA 刷新成 17。（这一步顺手把第一窗最优 t 更新到了 7。）
第二窗滑到 [3,4]，这两个数的和是 11。它左边能放的最好第一窗(绿色)和是 t = 7，两段相加 18。比之前更大，ansA 刷新成 18。
第二窗滑到 [4,5]，这两个数的和是 5。它左边能放的最好第一窗(绿色)和是 t = 9，两段相加 14。没超过当前 ansA = 18，先记着继续。（这一步顺手把第一窗最优 t 更新到了 9。）
第二窗滑到 [5,6]，这两个数的和是 4。它左边能放的最好第一窗(绿色)和是 t = 9，两段相加 13。没超过当前 ansA = 18，先记着继续。
再扫第二趟，把顺序反过来:这回长度 2 的窗口落在「前面」，长度 1 的窗口在它右边扫。角色对调:t 现在记「左边最好的长度 2 窗口和」，t 和 ansB 重新从 0 起。
第一窗滑到 [2,2]，和是 1。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 14。刷新 ansB 到 14。（这一步把第二窗最优 t 更新到了 13。）
第一窗滑到 [3,3]，和是 9。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 22。刷新 ansB 到 22。
第一窗滑到 [4,4]，和是 2。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 15。没超过 ansB = 22。
第一窗滑到 [5,5]，和是 3。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 16。没超过 ansB = 22。
第一窗滑到 [6,6]，和是 1。它左边最好的长度 2 窗口(绿色)和是 t = 13，两段相加 14。没超过 ansB = 22。
回放最优解:绿色是长度 2 的窗口 [6,7]，和 13，落在左边；右边方框是长度 1 的窗口 [9]，和 9。两段相加 22。注意它来自第二趟，长度 2 的窗口反而在前。这正是为什么两种顺序都得扫:只扫第一趟只会拿到 18。
边界想清楚:两段长度之和等于数组长度时答案固定为全数组和；含 0 也照常算；只有两段等长时两趟才完全等价。
面试重点:认出「固定一窗、另一窗取左侧历史最优」这个母结构，前缀和只是取窗口和的趁手工具。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int: n = len(nums) s = list(accumulate(nums, initial=0)) ans = t = 0 i = firstLen while i + secondLen - 1 < n: t = max(t, s[i] - s[i - firstLen]) ans = max(ans, t + s[i + secondLen] - s[i]) i += 1 t = 0 i = secondLen while i + firstLen - 1 < n: t = max(t, s[i] - s[i - secondLen]) ans = max(ans, t + s[i + firstLen] - s[i]) i += 1 return ans复杂度
- 时间：O(n)，建前缀和一遍 + 两趟各扫一遍，都是线性
- 空间：O(n)，前缀和数组 s 占 n+1 个位置；滚动变量 t、ans 是常数
易错点
面试追问把动画讲成自己的话
追问为什么固定一个窗口、另一个取「左边历史最优」就够了，不会漏解？
追问不用前缀和可以吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
不相交的线
LeetCode 1035 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题