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

约 5 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 哈希表 动态规划 二分查找 滑动窗口

题目描述

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

image-20260929110100934

image-20260929110101328

题意分析

在正整数数组中选出两个互不重叠的连续子数组，它们各自的和都必须等于 target，使长度之和最小。两段可以相邻，但不能共享下标；找不到两段时返回 -1。

解法：滑动窗口 + 前缀最短记录

核心思路

[!blue]

先考虑怎样找出和为目标值的候选段。所有元素都为正，右端扩展会增大窗口和，左端右移会减小窗口和。因此每加入一个右端元素，只要总和超过目标，就不断移除左端，直到不超过目标。若恰好相等，就得到以当前右端结尾的合法段。

固定右端时，左端右移会让和严格减小，所以至多存在一个等于目标的窗口。已经因和过大而移走的左端，也不必回退：以后右端加入更多正数，从那些旧左端开始的和只会更大。由此两个指针只前进，就能找到全部候选段；某个元素本身超过目标时，窗口会缩为空，再继续处理后续元素。

找到右侧候选 [left, right] 后，不能随意取此前发现的最短段，因为它仍可能与当前段重叠。定义 best[i] 为完全落在前缀 [0, i] 内、和为目标值的最短子数组长度。当前右段只能与 best[left - 1] 配对，这个位置之前结束的任何左段都与当前段没有公共下标。

用 bestSoFar 维护扫描到当前右端时已发现的最短合法段长度。命中窗口时，先用此前已经保存的 best[left - 1] 更新两段总长度，再用当前长度更新 bestSoFar；不论是否命中，每轮都把它写入 best[right]，让所有历史前缀都有准确记录。不存在合法段时用 INF 标记，配对前先检查它，避免把不存在的左段算进去。

任意一组可行答案都能分成左段和右段。扫描到它的右段终点时，该右段一定会被找到，而 best[left - 1] 记录的左段不会比这组答案使用的左段更长。因此枚举全部右段并取最小值，就不会漏掉全局最优组合。

解题步骤

  1. 初始化空窗口，把当前前缀最短长度 bestSoFar 和总答案设为 INF。
  2. 向右加入元素，总和超过目标时不断收缩左端。
  3. 总和等于目标时，若 left > 0 且左侧存在合法段，用当前长度加 best[left - 1] 更新答案。
  4. 用当前合法段更新 bestSoFar，每轮都写入 best[right]。
  5. 扫描完仍没有两段组合就返回 -1，否则返回最小总长度。

代码实现

class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        // 不可达记录只作哨兵，配对前需确认左侧候选存在。
        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)
    // 不可达记录只作哨兵，配对前需确认左侧候选存在。
    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)$，两个指针都最多经过数组一次，前缀最短值和答案每轮只需常数次更新。
  • 空间复杂度：$O(n)$，保存每个历史前缀的最短合法段长度。

关键点总结

[!green]

  • 元素为正，保证窗口和的单调性与固定右端下候选的唯一性。
  • best[i] 是整个前缀中的最短段，不只统计恰好在 i 结束的段。
  • 用 best[left - 1] 配对，将不重叠条件直接写进查询范围。

易错点总结

[!yellow]

  • 用全局 bestSoFar 直接配对，可能选到与当前窗口重叠的段。
  • left = 0 时没有左侧空间，不能访问负下标。
  • 只在命中时写 best[right]，会丢掉中间前缀继承的最优记录。
  • 第一次找到两段就返回，可能错过后面更短的组合。

相似题目

题目 难度 关联与区别
1031. 两个无重叠子数组的最大和 中等 原题两段长度固定并最大化和，本题两段和固定并最小化总长度，需维护前缀最短合格段。
560. 和为 K 的子数组 中等 目标和区间可由前缀关系定位，本题还要确保两个区间不重叠，不能直接选全局最短两段。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/16728717
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！