日期: 2026年9月17日

目标

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

示例 1：

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

示例 2：

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例 3：

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

示例 4：

输入：arr = [5,5,4,4,5], target = 3
输出：-1
解释：我们无法找到和为 3 的子数组。

示例 5：

输入：arr = [3,1,1,1,5,1,2,1], target = 3
输出：3
解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8

思路

有一个整数数组 arr 和一个整数值 target，从数组中找到两个不重叠的子数组，使得子数组的和为 target，返回这两个子数组长度之和的最小值。

将重叠问题进行前后缀分解，在各自的部分只需考虑和为 target 的最小长度，最小长度可以使用滑动窗口。

代码

/**
 * @date 2026-09-17 10:06
 */
public class MinSumOfLengths1477 {

    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        Arrays.fill(pre, Integer.MAX_VALUE);
        Arrays.fill(suf, Integer.MAX_VALUE);
        int sum = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[l++];
            }
            if (sum == target) {
                pre[i + 1] = Math.min(pre[i], i - l + 1);
            } else {
                pre[i + 1] = pre[i];
            }
        }
        sum = 0;
        int r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[r--];
            }
            if (sum == target) {
                suf[i] = Math.min(suf[i + 1], r - i + 1);
            } else {
                suf[i] = suf[i + 1];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (pre[i + 1] != Integer.MAX_VALUE && suf[i + 1] != Integer.MAX_VALUE) {
                res = Math.min(res, pre[i + 1] + suf[i + 1]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

性能