LeetCode 1477. 找两个和为目标值且不重叠的子数组

2026-07-15 HGNULB 约 9 分钟

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

分类

题目描述

✅ 1477. 找两个和为目标值且不重叠的子数组

题意分析

给定元素全为正整数的数组 arr 和目标值 target，要找出两个互不重叠的连续子数组，各自的和都恰好等于 target，返回两者长度之和的最小值；若不存在这样的两个子数组，返回 -1。

「元素全为正」这一条是本题的技术核心。它使得窗口和随右端点扩张严格单调递增、随左端点收缩严格单调递减，于是滑动窗口成立：对每个固定的右端点，和恰为 target 的窗口最多只有一个，可以在 $O(n)$ 内把所有候选子数组都找出来。若允许负数，就得改用前缀和加哈希，这也是同类题的分水岭。

「互不重叠」意味着两个子数组在下标上有先后：一个完全在另一个左侧。所以可以按右侧那个子数组来枚举——固定右侧子数组后，左侧那个只需要在它开始位置之前的范围内取最短，两者相互独立。

由此得到解题框架：一边用滑动窗口找出「以当前位置结尾、和为 target」的子数组，一边维护「到当前位置为止，和为 target 的最短子数组长度」。当窗口 [left, right] 命中 target 时，把它当作右侧子数组，配上 left - 1 处记录的左侧最短长度，即得一个候选答案。

边界：可能一个合法子数组都找不到，也可能只找到一个（[4,3,2,6,2,3,4], target = 6 只有孤立的一段），这两种情况都要返回 -1，不能返回半个答案。

解法：滑动窗口 + 前缀最优长度

核心思路

暴力做法是先枚举出所有和为 target 的子数组，再两两配对检查是否重叠，子数组数量最坏是 $O(n)$ 级但配对是 $O(n^2)$。浪费在于：固定右侧子数组后，左侧那个并不需要逐个试，只需要知道它左边范围内的最短长度这一个数。

于是引入辅助数组 best，定义 best[i] 为「在 arr[0..i] 这个前缀范围内，和为 target 的最短子数组长度」（不存在则为无穷大）。这个定义的关键在于它是前缀最优值，天生具有单调不增的累积性质，可以在同一次遍历中 $O(1)$ 递推：best[i] = min(best[i-1], 以 i 结尾的合法子数组长度)。

主循环用滑动窗口推进。因为元素全正，窗口和超过 target 时收缩左边界一定能减小和，所以 while (sum > target) 收缩之后，sum 要么小于 target（当前右端点无解），要么恰好等于 target（找到唯一一段）。

命中 target 时做两件事：把当前窗口当作右侧子数组，去查 best[left - 1] 得到候选答案；再用当前长度更新最短记录 bestSoFar。

这里唯一需要小心的是查的必须是 best[left - 1]，而不是「当前前缀的最优值」。best[left - 1] 是一个在下标 left - 1 那一轮就已经定格的快照，它只包含完全结束于 left - 1 及其之前的子数组，因此与当前窗口 [left, right] 必然不重叠——-1 这个偏移就是「不重叠」的全部含义。而 bestSoFar 累积到了当前位置，里面可能藏着一段与当前窗口重叠、甚至就是当前窗口本身的记录，用它配对会算出非法答案。若 left == 0，当前窗口贴着数组开头，左边没有空间，跳过配对。

最后 best[right] 无条件写入当前的最短记录，保证后续轮次能查到正确的前缀最优快照。

解题步骤

初始化：INF 取一个安全大值（不要用 Integer.MAX_VALUE，后面要做加法，会溢出）。best 数组长度为 n，bestSoFar = INF 表示当前前缀内还没找到合法子数组，ans = INF，窗口 sum = 0、left = 0。

扩张窗口：right 从 0 扫到 n-1，sum += arr[right]。

收缩窗口：while (sum > target) 时 sum -= arr[left]、left++。元素全正保证了这个收缩必然让 sum 单调减小，不会死循环；left 可能越过 right，此时窗口为空、sum 为 0，逻辑依然成立。

命中处理：若 sum == target，当前窗口长度是 right - left + 1。

配对：若 left > 0 且 best[left-1] 不是 INF，用 当前长度 + best[left-1] 更新 ans。查 best[left-1] 而非 bestSoFar，才能保证左侧子数组在下标 left-1 处就已结束，与当前窗口不重叠。

更新记录：用当前长度更新 bestSoFar，供后续位置配对使用。

记录前缀最优：不论本轮是否命中，都执行 best[right] = bestSoFar。漏掉这一步会让后续查询读到未初始化的值。

返回：ans 仍为 INF 说明凑不出两段，返回 -1；否则返回 ans。

以 arr = [7,3,4,7]、target = 7 走一遍：

right=0：sum=7 命中，长度 1，但 left=0 没有左侧空间，只更新 bestSoFar=1；best[0]=1。
right=1：sum=10 > 7，收缩掉 arr[0]=7，sum=3、left=1，未命中；best[1]=1。
right=2：sum=7 命中，长度 2-1+1=2，left=1>0 且 best[0]=1，得候选 2+1=3，ans=3；bestSoFar=min(1,2)=1；best[2]=1。
right=3：sum=14 > 7，收缩掉 arr[1]=3 得 11，仍大于 7，再收缩掉 arr[2]=4 得 sum=7、left=3。命中，长度 1，best[2]=1，候选 1+1=2，ans=2。

最终返回 2，对应 [7]（下标 0）与 [7]（下标 3）。注意 right=2 时算出的 3 被后面的 2 覆盖了，说明必须扫完全程取最小，不能提前返回。

再看只能找到一段的用例 arr = [4,3,2,6,2,3,4]、target = 6：唯一命中发生在 right=3（窗口是下标 3 的单个 6，left=3），此时 best[2] 仍是 INF，候选被正确跳过；此后再无命中，ans 保持 INF，返回 -1。

代码实现

class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        // 除以 2 留出加法余量，避免两个 INF 相加溢出。
        final int INF = Integer.MAX_VALUE / 2;
        // best[i] 表示 arr[0..i] 内和为 target 的最短子数组长度。
        int[] best = new int[n];
        int bestSoFar = INF;
        int ans = INF;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < n; right++) {
            sum += arr[right];
            while (sum > target) {
                // 元素全为正，收缩左边界一定使窗口和减小。
                sum -= arr[left];
                left++;
            }

            if (sum == target) {
                int len = right - left + 1;
                if (left > 0 && best[left - 1] != INF) {
                    // 读 best[left-1] 这个历史快照，左段必然结束于窗口开始之前。
                    ans = Math.min(ans, len + best[left - 1]);
                }
                // 当前长度只供后续位置配对使用。
                bestSoFar = Math.min(bestSoFar, len);
            }

            best[right] = bestSoFar;
        }

        return ans == INF ? -1 : ans;
    }
}

func minSumOfLengths(arr []int, target int) int {
    n := len(arr)
    // 留出加法余量，避免两个 inf 相加溢出。
    const inf = 1 << 29
    // best[i] 表示 arr[0..i] 内和为 target 的最短子数组长度。
    best := make([]int, n)
    bestSoFar := inf
    ans := inf
    sum := 0
    left := 0

    for right := 0; right < n; right++ {
        sum += arr[right]
        for sum > target {
            // 元素全为正，收缩左边界一定使窗口和减小。
            sum -= arr[left]
            left++
        }

        if sum == target {
            length := right - left + 1
            if left > 0 && best[left-1] != inf && length+best[left-1] < ans {
                // 读 best[left-1] 这个历史快照，左段必然结束于窗口开始之前。
                ans = length + best[left-1]
            }
            // 当前长度只供后续位置配对使用。
            if length < bestSoFar {
                bestSoFar = length
            }
        }

        best[right] = bestSoFar
    }

    if ans == inf {
        return -1
    }
    return ans
}

复杂度分析

时间复杂度：$O(n)$。right 扫描 n 次，left 只增不减、总位移不超过 n，所以内层 while 的总执行次数是 $O(n)$ 而非每轮 $O(n)$；best 的递推是 $O(1)$。相比「找出所有候选段再两两配对」的 $O(n^2)$，省掉的是配对那一层。

空间复杂度：$O(n)$，用于 best 数组。可以优化到 $O(1)$——只要把「左侧最短」改成随窗口滚动的两个变量——但会让不重叠的边界更难写清，$O(n)$ 版本更适合面试直接写。

关键点总结

元素全为正是滑动窗口的许可证：它保证了窗口和的单调性，从而每个右端点最多对应一段和为 target 的窗口。若含负数或零，必须换成前缀和加哈希。

「两段不重叠」通过枚举右侧段、查询 best[left-1] 来落实，-1 这个偏移就是不重叠的全部含义所在。

best 存的是前缀最优值而不是「以 i 结尾的长度」，正因为它累积了历史最优，配对才能 $O(1)$ 完成。

配对时读的是 best 数组里已经定格的历史快照，而不是仍在滚动的当前最优值——这是防止同一段子数组既当左段又当右段的关键。

找不到两段必须返回 -1，用哨兵初值加末尾判断来表达，不要中途提前返回。

易错点总结

用 bestSoFar 代替 best[left-1] 配对：bestSoFar 累积到了当前位置，可能是一段与当前窗口重叠的记录。用 arr = [1,1,1], target = 2 检验：两段候选 [0,1] 与 [1,2] 在下标 1 处重叠，正确答案是 -1，而这种写法会返回 2 + 2 = 4。

查询写成 best[left] 或 best[right]：同样会允许左侧段与当前窗口重叠，必须是 best[left-1]。

left == 0 时不判断：直接访问 best[-1] 会越界。窗口贴着数组开头时左边没有空间，应跳过配对。

INF 取 Integer.MAX_VALUE：len + best[left-1] 立刻整型溢出变成负数，ans 被污染成一个极小值。要留出加法余量。

漏掉每轮的 best[right] = bestSoFar：只在命中时写入，未命中的位置会残留 0（Java 数组默认值），后续查询把 0 当成合法长度，答案严重偏小。

忘记 best[left-1] 可能是 INF：不判断就参与相加，会得到一个巨大但仍小于初始 ans 的假答案。

命中后立即返回：本题要的是全局最小和，必须扫完整个数组。[7,3,4,7] 会因此返回 3 而不是 2。

以为要返回子数组本身或两段的和：题目要的是两段长度之和。

相似题目

题目	难度	考察点
209. 长度最小的子数组	中等	只找一段的基础版，本题主循环的窗口骨架就来自这里
1031. 两个无重叠子数组的最大和	中等	同样是「两段不重叠 + 前缀最优」，但段长固定、目标改为求最大
689. 三个无重叠子数组的最大和	困难	推广到三段，需要同时维护前缀最优与后缀最优
560. 和为 K 的子数组	中等	含负数时窗口失效，改用前缀和加哈希，正好是本题的反面对照
862. 和至少为 K 的最短子数组	困难	含负数且要求最短，需要前缀和配单调队列