更新题目 689. Maximum Sum of 3 Non-Overlapping Subarrays

题目 lc689 · 修改（rev 2） · cc · 2026-10-26 23:11
body

@@ -1,5 +1,12 @@
 ## 题目
 
-在数组里找三个互不重叠、长度都是 k 的子数组，使它们的和最大，返回三个起点（和相同时取字典序最小的）。
+给一个整数数组 `nums` 和一个长度 `k`，找三个互不重叠、长度都是 `k` 的连续子数组，让三段的和加起来最大，返回三段的起点下标（从 0 开始，从左到右）。和最大的选法不止一种时，返回字典序最小的那组起点，也就是先比第一段的起点，小的胜出，相同再比第二段，依此类推。
+
+LeetCode 的约束：`1 <= nums.length <= 2 * 10^4`，`1 <= nums[i] < 2^16`，`1 <= k <= floor(nums.length / 3)`，所以三段一定放得下。
+
+| 输入 | 输出 | 为什么 |
+| --- | --- | --- |
+| `nums = [1,2,1,2,6,7,5,1]`，`k = 2` | `[0, 3, 5]` | 三段是 `[1,2]`、`[2,6]`、`[7,5]`，和 3 + 8 + 12 = 23。`[1, 3, 5]` 也是 23，但起点 0 比 1 小 |
+| `nums = [1,2,1,2,1,2,1,2,1]`，`k = 2` | `[0, 2, 4]` | 每个长度 2 的窗口和都是 3，任选三段都是 9，取最靠左的一组 |
 
 [LeetCode 原题](https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/)
@@ -7,53 +14,131 @@
 ## 面经里怎么考的
 
-Visa Staff OA（2026-05，楼主挂了）：楼主用谐音写「类似琉芭韭」，读作 689，改动是「k 是三个不同参数」，也就是三个子数组的长度各不相同。同一场另一题是有向带权图上的 Dijkstra（没给更多细节）。
+Visa Staff OA（2026-05，楼主挂了）：楼主用谐音写「类似琉芭韭」，读作 689，说改动是「k 是三个不同参数」，现有记录里关于改动只有这一句。这里理解成三个子数组的长度各自给定，记作 `k1`、`k2`、`k3`，从左到右依次是长 `k1`、`k2`、`k3` 的三段【推断】。同一场另一题是有向带权图上的 Dijkstra（没给更多细节）。
+
+现有记录没有写三个参数具体管什么、三段的先后顺序是否固定、要返回什么、并列时怎么选（未核实）。顺序可以任选的话，对 3! = 6 种顺序各算一遍，取和最大的那组。
 
 ## 思路
 
-先用滑动窗口算出每个起点 i 的窗口和 `w[i]`。固定中间那段的起点 j，左边那段要在 `[0, j − k]` 里选 `w` 最大的起点，右边那段在 `[j + k, end]` 里选最大的；这两个「到某处为止的最大值位置」可以预先从左、从右各扫一遍算好。最后枚举 j。
+先用滑动窗口（sliding window）算出每个起点 `i` 的窗口和 `w[i]`，也就是 `nums[i]` 到 `nums[i + k − 1]` 的和。窗口右移一格时加上新进来的数、减去出去的数，整张表 `O(n)` 算完。之后题目变成：在 `w` 里挑三个下标 `i < j < l`，要求相邻两个至少差 `k`（保证不重叠），让 `w[i] + w[j] + w[l]` 最大。
 
-三段长度不同（k1、k2、k3）时思路不变：`w1`、`w2`、`w3` 各算一份，左边用 `w1` 的前缀最大，右边用 `w3` 的后缀最大，中间枚举 `w2` 的起点，范围按各自的长度改。
+关键一步是固定中间那段的起点 `j`。`j` 定了以后，左段只能从 `[0, j − k]` 里选，右段只能从 `[j + k, n − k]` 里选，两边互不影响，所以左边取这个范围里 `w` 最大的起点，右边也取它的范围里最大的，加上 `w[j]` 就是以 `j` 为中段时的最优解。任何一组合法答案都有一个中段，所以把所有 `j` 都枚举一遍，最大的那个就是全局最优。
+
+「`w[0..x]` 里最大值在哪」和「`w[x..]` 里最大值在哪」可以预先各扫一遍存成两个数组：`best_left[x]` 从左往右扫，`best_right[x]` 从右往左扫。这样每个 `j` 只要 `O(1)` 查两次表，总时间 `O(n)`。
+
+> [!say] I precompute every window sum. For each choice of the middle window, the best left window and the best right window are independent, so I look them up in a prefix-argmax array and a suffix-argmax array. That makes the whole scan linear.
+
+### 并列时怎么保证字典序最小
+
+三处都要在并列时留下更小的下标：
+
+- `best_left` 从左往右扫，遇到严格更大（`>`）才换，相等时留着先见到的、更靠左的那个。
+- `best_right` 从右往左扫，遇到大于或等于（`>=`）就换。从右往左走，后见到的反而更靠左，所以相等也要换。
+- 枚举 `j` 从小到大，总和严格更大（`>`）才更新答案，相等时留着更小的 `j`。
+
+这三条合起来确实给出字典序最小，理由如下。设算法返回 `(i, j, l)`，另有一组和同样最大的 `(i', j', l')`。第三条保证 `j` 是所有最优解里最小的中段，所以 `j <= j'`。
+
+- 假如 `i' < i`：`i' < i <= j − k`，`i'` 也在 `j` 的左段范围里。`best_left` 在并列时留更小的下标，选了 `i` 而没选更小的 `i'`，说明 `w[i'] < w[i]`。又因为 `i <= j − k <= j' − k`，把 `(i', j', l')` 的左段换成 `i` 仍然合法，和变大了，与它是最优解矛盾。所以 `i <= i'`。
+- `i < i'` 时 `(i, j, l)` 已经更小。`i = i'` 时看中段，`j < j'` 也已经更小。`j = j'` 时把同样的道理用在右段上：`l'` 在 `j` 的右段范围里，`best_right` 在并列时留更小的下标，得到 `l <= l'`。
+
+所以 `(i, j, l)` 的字典序不大于任何一组最优解。
+
+### 三段长度不同时
+
+思路不变，只是三段各用自己的窗口和表：`w1`、`w2`、`w3` 分别是长度 `k1`、`k2`、`k3` 的窗口和。左段用 `w1` 的前缀最大，右段用 `w3` 的后缀最大，中段枚举 `w2` 的起点 `j`。范围要按各自的长度改：
+
+- 中段起点 `j` 从 `k1` 到 `n − k2 − k3`。左边要放得下长 `k1` 的一段，右边要放得下 `k2 + k3`。
+- 左段起点不超过 `j − k1`，查 `best_left[j − k1]`。
+- 右段起点不小于 `j + k2`，查 `best_right[j + k2]`。
+
+在三个长度按从左到右的顺序给出的前提下，这样做是对的：上面「固定中段、两边各取最大」的理由和字典序的论证都只用到「左段在中段之前结束、右段在中段之后开始」，没有用到三段等长。原题就是 `k1 = k2 = k3 = k` 的特例，所以下面的代码只写一份通用版本，原题调用它。
+
+> [!say] If the three windows have different lengths, I keep one window-sum array per length. The middle start ranges from k1 to n minus k2 minus k3, the left window must end before the middle starts, and the right window must start after the middle ends.
 
 ## 代码
 
 ```python
-def max_sum_of_three_subarrays(nums, k):
-    n = len(nums)
-    w = [0] * (n - k + 1)
-    s = sum(nums[:k]); w[0] = s
-    for i in range(1, n - k + 1):
-        s += nums[i + k - 1] - nums[i - 1]
-        w[i] = s
-    left, best = [0] * len(w), 0
-    for i in range(len(w)):
-        if w[i] > w[best]:
-            best = i
-        left[i] = best
-    right, best = [0] * len(w), len(w) - 1
-    for i in range(len(w) - 1, -1, -1):
-        if w[i] >= w[best]:          # >= 让并列时取更小的下标
-            best = i
-        right[i] = best
-    ans = None
-    for j in range(k, len(w) - k):
-        i, l = left[j - k], right[j + k]
-        total = w[i] + w[j] + w[l]
-        if ans is None or total > ans[0]:
-            ans = (total, [i, j, l])
-    return ans[1]
+from typing import List, Sequence, Tuple
+
+
+def window_sums(nums: Sequence[int], length: int) -> List[int]:
+    """sums[i] = nums[i] + ... + nums[i + length - 1], for every valid start i."""
+    total = sum(nums[:length])
+    sums = [total]
+    for start in range(1, len(nums) - length + 1):
+        total += nums[start + length - 1] - nums[start - 1]
+        sums.append(total)
+    return sums
+
+
+def prefix_argmax(values: List[int]) -> List[int]:
+    """best[i] = index of the max of values[0..i]; ties keep the smaller index."""
+    best, best_idx = [], 0
+    for i, v in enumerate(values):
+        if v > values[best_idx]:  # strict: an equal value later does not replace
+            best_idx = i
+        best.append(best_idx)
+    return best
+
+
+def suffix_argmax(values: List[int]) -> List[int]:
+    """best[i] = index of the max of values[i..]; ties keep the smaller index."""
+    best, best_idx = [0] * len(values), len(values) - 1
+    for i in range(len(values) - 1, -1, -1):
+        if values[i] >= values[best_idx]:  # >=: an equal value further left wins
+            best_idx = i
+        best[i] = best_idx
+    return best
+
+
+def max_sum_of_three_windows(nums: Sequence[int],
+                             lengths: Tuple[int, int, int]) -> List[int]:
+    """Starts of three non-overlapping windows, left to right, with lengths
+    lengths[0], lengths[1], lengths[2], maximizing the total sum.
+    Ties go to the lexicographically smallest list of starts.
+    Raises ValueError if the windows cannot fit into nums.
+    """
+    k1, k2, k3 = lengths
+    if min(lengths) < 1 or k1 + k2 + k3 > len(nums):
+        raise ValueError("three windows of these lengths do not fit")
+    left_sums = window_sums(nums, k1)
+    mid_sums = window_sums(nums, k2)
+    right_sums = window_sums(nums, k3)
+    best_left = prefix_argmax(left_sums)
+    best_right = suffix_argmax(right_sums)
+
+    best_total, best_starts = None, []
+    for mid in range(k1, len(nums) - k2 - k3 + 1):
+        left = best_left[mid - k1]       # left window must end before mid
+        right = best_right[mid + k2]     # right window must start after mid's end
+        total = left_sums[left] + mid_sums[mid] + right_sums[right]
+        if best_total is None or total > best_total:  # strict: keep earliest mid
+            best_total, best_starts = total, [left, mid, right]
+    return best_starts
+
+
+def max_sum_of_three_subarrays(nums: Sequence[int], k: int) -> List[int]:
+    """LeetCode 689: three windows of the same length k."""
+    return max_sum_of_three_windows(nums, (k, k, k))
 ```
 
-本机跑过官方例子。
+OA 的代码写法也计分，所以代码这样拆：
+
+- 窗口和、前缀最大、后缀最大各是一个小函数，名字说明它算什么，docstring 写清并列时留哪个下标。主函数只剩「固定中段、查两张表、比总和」，和思路一节的三步一一对应。
+- 通用版本接收三个长度，按从左到右的顺序。OA 的三个参数如果就是这样给的，可以直接调用它【推断】。
+- 放不下三段（某个长度小于 1，或者三段长度加起来超过 `n`）时抛 `ValueError`，不返回一个看起来像答案的列表。LeetCode 保证放得下，不会走到这里。题面要求无解时返回空列表或 `-1` 的话，把这一行换掉即可。
+
+2026-10-26 用 Python 3.13.17 跑过上面这段代码：
+
+- 两个官方例子分别得 `[0, 3, 5]` 和 `[0, 2, 4]`。`[5, 4, 3]` 配 `k = 1`（三段刚好占满）得 `[0, 1, 2]`。长度 5 的数组配 `k = 2` 抛 `ValueError`。
+- 和暴力解对拍。暴力解枚举所有合法的三元组，按（和取负，起点列表）取最小。等长版本 3000 组随机输入（`k` 从 1 到 3，元素取 0 到 3，小值域故意制造大量并列），三段不等长版本 3000 组（三个长度各从 1 到 3，元素取 −3 到 3，含负数），结果全部一致。
+- `n = 2 * 10^4`、元素在 1 到 `2^16 − 1` 之间的随机数组，`k = 1000` 和 `k = 1` 各约 11 毫秒。
 
 ## 复杂度
 
-O(n)。
+时间 `O(n)`：三张窗口和表、两张最大值位置表各扫一遍，枚举中段一遍，每个中段查表 `O(1)`。额外空间 `O(n)`，存这五张表。
 
 ## 易错点
 
-- 字典序最小：左边用 `>`、右边用 `>=`。
-- 三段长度不同的变种里，中间段的枚举范围要按 k1、k2、k3 分别算。
-
-## 英文讲法
-
-> [!say] I precompute every window sum, then for each choice of the middle window I take the best window entirely to its left and the best entirely to its right, using prefix and suffix argmax arrays.
+- **并列时的比较符号**。左边的前缀最大用 `>`、右边的后缀最大用 `>=`，理由见「并列时怎么保证字典序最小」。2026-10-26 在两个官方例子上并排跑过：左边误用 `>=` 时，例子一得 `[1, 3, 5]`（`w[0]` 和 `w[1]` 都是 3，留了靠后的 1），正确版本得 `[0, 3, 5]`。右边误用 `>` 时，例子二得 `[0, 2, 7]`，正确版本得 `[0, 2, 4]`。每个例子只能抓到其中一个错，两个都要跑。
+- **三段长度不同时的下标范围**。中段从 `k1` 枚举到 `n − k2 − k3`，左段查 `j − k1`，右段查 `j + k2`。从等长版本改过来时，容易有一处还留着同一个 `k`。写完拿小例子手动核对一遍边界，见 [[p:me/python-pitfalls]]「边界和差一」。
+- **放不下三段**。LeetCode 保证 `3k <= n`，所以只照 LeetCode 写的版本往往不检查。如果答案存成 `ans = None`、枚举中段时更新、最后 `return ans[1]`，在 `n < 3k` 的输入上一个中段都枚举不到，`ans` 停在 `None`，最后一行抛 `TypeError`（2026-10-26 实测，`n = 5`、`k = 2`）。OA 题面没写保证放得下时，像上面的代码一样在开头检查。
更新题目 689. Maximum Sum of 3 Non-Overlapping Subarrays

body

meta
