1477.找两个和为目标值且不重叠的子数组：滑动窗口 + 记录前值(动态规划)

【LetMeFly】1477.找两个和为目标值且不重叠的子数组：滑动窗口 + 记录前值(动态规划)

力扣题目链接：https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/

给你一个整数数组 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

解题方法：滑动窗口

如果这道题只需要求一个和为target的最短子数组的长度，那么一个滑动窗口就可以解决：

用两个指针l和r表示滑动窗口的左右边界，用变量cnt表示当前窗口内元素的和。

每次右指针r右移一位，当cnt > target时，不断右移左指针。如果cnt == target，则更新最短子数组的长度。

现在变成了两个和为target的不重叠子数组，怎么办？也好办，用一个数组把 从下标0到l为止最短的target和子数组 记录下来就好了。

当滑动窗口中和为target时候，我们要做的事情就变成了两个：

• 一是更新答案最小值，可能是 当前窗口中的一段($r-l+1$) + 当前窗口之前范围内的最短子数组长度($minL[l]$)
• 二是更新从$0$到$r$为止的最短子数组长度$minL[r+1]$，可能是当前窗口中的这一段($r-l+1$)，或者是之前的最短子数组长度($minL[r]$)

以上。

• 时间复杂度$O(len(arr))$，每个元素最多入队一次出队一次；
• 空间复杂度$O(len(arr))$。

AC代码

C++

/*
 * @LastEditTime: 2026-09-17 13:26:14
 */
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n = arr.size();
        vector<int> minL(n + 1, 1e7);
        int ans = 1e7;
        for (int l = 0, r = 0, cnt = 0; r < n; r++) {
            cnt += arr[r];
            while (cnt > target) {
                cnt -= arr[l++];
            }
            minL[r + 1] = minL[r];
            if (cnt == target) {
                minL[r + 1] = min(minL[r + 1], r - l + 1);
                ans = min(ans, minL[l] + r - l + 1);
            }
        }
        return ans > n ? -1 : ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源