LeetCode 689. 三个无重叠子数组的最大和

2021-08-06 HGNULB 约 11 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 689. 三个无重叠子数组的最大和

题意分析

要什么：从数组中挑出三个长度都恰为 k、互不重叠的连续子数组，使三者元素之和最大，返回它们的起始下标（升序排列）。若有多组方案取得同样的最大和，返回字典序最小的那一组下标。
约束透露的信号：三个窗口长度相同且固定，说明第一步一定是把「每个起点的窗口和」预处理出来，把问题从「在原数组上选区间」压缩成「在窗口和数组上选三个下标」。窗口互不重叠翻译成下标语言就是：若三个起点为 l < j < r，必须满足 l + k ≤ j 且 j + k ≤ r。「字典序最小」这个附加要求决定了并列时必须取更小的下标，而且左中右三处的取舍规则要各自对齐。数组规模到 $10^4$ 以上，需要线性做法。
边界：数组长度至少是 3k 才有解，题目已保证；元素均为非负整数，所以窗口和非负，但答案变量仍不该随意初始化；三个窗口可以首尾紧贴（l + k == j 合法），不需要留空隙。

解法：滑动窗口 + left/right 预处理

核心思路

暴力是三重循环枚举三个起点，每次再求三段和，$O(n^3)$ 甚至 $O(n^3 k)$，完全不可行。先用定长滑动窗口把 sums[i]（以 i 开头、长度 k 的窗口和）预处理出来，暴力降到 $O(n^3)$，仍然太慢。
瓶颈在于：一旦固定中间窗口的起点 j，左窗口只能在 [0, j-k] 里选、右窗口只能在 [j+k, 末尾] 里选，而这两侧的最优选择与 j 具体是多少无关，只与「可选区间的边界」有关。暴力却对每个 j 都把两侧重新扫了一遍。
于是枚举中间窗口，把两侧的最优解预先算好：

left[i] = 在 sums[0..i] 中窗口和最大的下标，并列时取最小下标（前缀最大值的位置）。

right[i] = 在 sums[i..末尾] 中窗口和最大的下标，并列时取最小下标（后缀最大值的位置）。
这两个数组就是要维护的不变量，各自一趟线性扫描即可求出。之后枚举 j，答案的三元组直接是 (left[j-k], j, right[j+k])，取三者和最大的那次。
字典序怎么保证？三个位置的并列规则要分别处理。left 从左往右扫，只在严格大于时更新，于是同和的最靠左下标被保留；right 从右往左扫，在大于等于时更新，由于是逆序推进，最后留下的同样是同和中最靠左的下标；主循环也只在总和严格大于当前最大值时才改写答案，j 从小到大枚举，同和时保留更小的 j。三处规则叠加，得到的下标三元组即字典序最小。

解题步骤

先用定长滑动窗口构造 sums，长度为 n - k + 1。为什么先做这一步：把「区间求和」这个 $O(k)$ 的操作变成 $O(1)$ 的查表，后续所有推理都在这个更短的数组上进行，问题从二维（起点 + 长度）降到一维。

正向扫描构造 left：维护 bestLeft，只在 sums[i] > sums[bestLeft] 时更新，然后写 left[i] = bestLeft。为什么用严格大于：并列时不更新，bestLeft 就停在更早的位置，满足字典序最小。

反向扫描构造 right：维护 bestRight，在 sums[i] >= sums[bestRight] 时更新，然后写 right[i] = bestRight。为什么这里反而用大于等于：扫描方向是从右往左，后被访问的下标更小，用 >= 才能让同和时的更小下标覆盖掉更大下标；如果照抄 left 的严格大于，留下的会是靠右的下标，字典序变大。

枚举中间起点 j，范围是 k <= j 且 j + k < sums.length。为什么下界是 k：左边必须放得下一个完整窗口，最小的左起点是 0，故 j 至少为 k。为什么上界是 j + k < sums.length：右起点至少是 j + k，它必须是 sums 的合法下标。

取 l = left[j - k]、r = right[j + k]，算总和并在严格更大时更新答案。为什么左边查的是 left[j-k] 而不是 left[j-1]：左窗口覆盖 [l, l+k-1]，要与中间窗口 [j, j+k-1] 不重叠就必须 l + k - 1 < j，即 l ≤ j - k。写成 left[j-1] 会允许 l 大到 j-1，此时两个窗口重叠 k-1 个元素，算出的「最大和」根本不对应任何合法方案。

返回三元组。

以 nums = [1, 2, 1, 2, 6, 7, 5, 1]、k = 2 走一遍。先算窗口和：sums = [3, 3, 3, 8, 13, 12, 6]（例如 sums[4] = 6 + 7 = 13）。正向构造 left：sums[0] = 3 起手，下标 1、2 的值同为 3 不触发严格大于，故 left[0..2] = 0；sums[3] = 8 > 3 使 left[3] = 3；sums[4] = 13 > 8 使 left[4] = 4；后面 12、6 都不更大，left[5] = left[6] = 4。得 left = [0, 0, 0, 3, 4, 4, 4]。反向构造 right：从 i = 6 起 bestRight = 6；i = 5 时 12 >= 6 更新为 5；i = 4 时 13 >= 12 更新为 4；i = 3 时 8 >= 13 不成立，保持 4；再往左都保持 4。得 right = [4, 4, 4, 4, 4, 5, 6]。主循环 j 取 2、3、4：j = 2 时 l = left[0] = 0、r = right[4] = 4，总和 3 + 3 + 13 = 19，记下 [0, 2, 4]；j = 3 时 l = left[1] = 0、r = right[5] = 5，总和 3 + 8 + 12 = 23 更大，答案更新为 [0, 3, 5]；j = 4 时 l = left[2] = 0、r = right[6] = 6，总和 3 + 13 + 6 = 22 不超过 23，不更新。返回 [0, 3, 5]，对应三段 [1,2]、[2,6]、[7,5]，和为 23。顺带看一眼错误写法的后果：若把 l 取成 left[j-1]，j = 4 时会拿到 left[3] = 3，得到 8 + 13 + 6 = 27 这个看似更大的值，但下标 3 的窗口是 [2,6]、下标 4 的窗口是 [6,7]，它们共用了元素 6，方案非法。

代码实现

// 核心实现：滑动窗口 + left/right 预处理，维护必要状态并避免重复处理。
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sums = new int[n - k + 1];

        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sums[0] = windowSum;
        for (int i = 1; i <= n - k; i++) {
            windowSum += nums[i + k - 1] - nums[i - 1];
            sums[i] = windowSum;
        }

        int[] left = new int[sums.length];
        int bestLeft = 0;
        for (int i = 0; i < sums.length; i++) {
            if (sums[i] > sums[bestLeft]) {
                bestLeft = i;
            }
            left[i] = bestLeft;
        }

        int[] right = new int[sums.length];
        int bestRight = sums.length - 1;
        for (int i = sums.length - 1; i >= 0; i--) {
            if (sums[i] >= sums[bestRight]) {
                bestRight = i;
            }
            right[i] = bestRight;
        }

        int[] answer = new int[] {-1, -1, -1};
        int maxSum = -1;
        for (int j = k; j + k < sums.length; j++) {
            int l = left[j - k];
            int r = right[j + k];
            int total = sums[l] + sums[j] + sums[r];
            if (total > maxSum) {
                maxSum = total;
                answer[0] = l;
                answer[1] = j;
                answer[2] = r;
            }
        }

        return answer;
    }
}

// 核心实现：滑动窗口 + left/right 预处理，维护必要状态并避免重复处理。
func maxSumOfThreeSubarrays(nums []int, k int) []int {
    n := len(nums)
    sums := make([]int, n-k+1)

    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }
    sums[0] = windowSum
    for i := 1; i <= n-k; i++ {
        windowSum += nums[i+k-1] - nums[i-1]
        sums[i] = windowSum
    }

    left := make([]int, len(sums))
    bestLeft := 0
    for i := 0; i < len(sums); i++ {
        if sums[i] > sums[bestLeft] {
            bestLeft = i
        }
        left[i] = bestLeft
    }

    right := make([]int, len(sums))
    bestRight := len(sums) - 1
    for i := len(sums) - 1; i >= 0; i-- {
        if sums[i] >= sums[bestRight] {
            bestRight = i
        }
        right[i] = bestRight
    }

    result := []int{-1, -1, -1}
    maxSum := -1
    for j := k; j+k < len(sums); j++ {
        l := left[j-k]
        r := right[j+k]
        total := sums[l] + sums[j] + sums[r]

        if total > maxSum {
            maxSum = total
            result[0] = l
            result[1] = j
            result[2] = r
        }
    }

    return result
}

复杂度分析

时间复杂度：$O(n)$。凭什么：构造 sums 用定长滑窗一趟；left 与 right 各一趟；主循环再一趟，每轮只做常数次查表和加法，四趟线性扫描相加仍是线性。

空间复杂度：$O(n)$。凭什么：sums、left、right 三条数组长度都是 n - k + 1；答案只占常数空间。

关键点总结

「选多段互不重叠区间」的通用套路是固定中间一段、把两侧压成前后缀极值。当段数是 3 时这招最划算；段数变多（比如 m 段）就该换成 dp[i][t] 表示前 i 个窗口里选 t 段的最优值。识别段数决定选哪种模板。

不重叠约束必须换算成下标不等式再落地：l + k ≤ j 与 j + k ≤ r。本题最经典的错误就是凭直觉写成 left[j-1]，看起来「左边取到 j 之前的最大值」很合理，实则允许窗口重叠。写下标类代码时，务必把区间端点显式写出来验算一次。

字典序最小要在每个决策点分别落实，而且并列规则与扫描方向绑定：正扫用严格大于、逆扫用大于等于，才能都保留更小的下标。三处规则不一致就会得到「和正确但下标不是最小」的答案。

定长窗口和数组 sums 是一层很有价值的抽象：它把原问题从「二维区间选择」降成「一维点选择」，之后所有推理都变得干净。遇到「若干个定长子数组」的题，先建 sums 几乎总是对的第一步。

面试视角：先说三重暴力，再说「固定中间、两侧取前后缀最优」的降维思路，最后单独强调「不重叠约束怎么落到下标上」和「字典序怎么保证」。这两点正是面试官会拿反例追问的地方，主动讲清楚比写完代码等着被 hack 好得多。

易错点总结

错误写法：左侧取 left[j - 1]；用例 nums = [1,2,1,2,6,7,5,1]、k = 2 → j = 4 时取到 left[3] = 3，左窗口 [2,6] 与中间窗口 [6,7] 共用元素 6，算出非法的 27 并返回 [3,4,6]，正确答案是 [0,3,5]。

错误写法：右侧取 right[j + 1]；用例 nums = [1,2,1,2,6,7,5,1]、k = 2 → 中间与右侧窗口重叠，同样得到偏大的伪最优解。

错误写法：构造 right 时用严格大于；用例 nums = [1,2,1,2,1,2,1,2,1]、k = 2 → 所有窗口和相等，right 保留的是最靠右的下标，返回 [0,2,6] 之类，正确答案是字典序最小的 [0,2,4]。

错误写法：构造 left 时用大于等于；用例全等元素数组 → left 保留最靠右的下标，左窗口起点被推大，字典序不再最小。

错误写法：主循环更新答案时用 total >= maxSum；用例全等元素数组 → 同和时不断被更大的 j 覆盖，返回的中间下标偏大。

错误写法：主循环上界写成 j < sums.length；用例任意输入 → right[j+k] 越界，抛数组下标异常。

错误写法：主循环下界写成 j = 0 或 j = 1；用例 k = 2 → left[j-k] 的下标为负，直接越界。

错误写法：sums 数组长度开成 n - k；用例 nums 长度恰为 3k → 最后一个合法窗口起点被截掉，右侧最优解丢失，答案偏小。

错误写法：滑窗递推写成 windowSum += nums[i + k] - nums[i]；用例 nums = [1,2,3,4]、k = 2 → 进出的元素各错一位，sums 整体偏移，后续全部基于错误数据。

错误写法：改用「先选全局最大的窗口，再在剩余区域各选一个」的贪心；用例 nums = [1,2,1,2,6,7,5,1]、k = 2 → 先选走和为 13 的 [6,7] 后，左右两侧被切碎，得到的总和小于 23，贪心在这里不成立。

错误写法：把三个窗口的和用原数组重新累加而不是查 sums；用例 n = 2 \times 10^4、k = 5000 → 每轮多花 $O(k)$，总代价退化到 $O(nk)$，超时。

相似题目

题目	难度	考察点
1031. 两个无重叠子数组的最大和	中等	只有两段且长度可以不同，一趟扫描维护「另一段的前缀最优」即可，无需预处理数组
643. 子数组最大平均数 I	简单	只选一段定长窗口，是本题第一步预处理的独立版本
53. 最大子数组和	中等	段长不再固定，滑窗失效，改用「要么接上前面要么另起一段」的线性 DP