题目描述
思路解析动画文字版
把整套思路压成两句:前缀和让窗口和「一减就得」；扫的时候一个窗口固定、另一个取左侧历史最优 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题