目标
给你一个整数数组 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;
}
}
性能
