题目描述

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

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

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

样例

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

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

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

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

输入：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

算法

(双指针) $O(n)$

1. 对于每个位置 $i$，我们找到最小的位置 $j$ 满足区间 [j, i] 的和小于等于 target。同时维护一个数组 min_len，min_len[i] 表示右区间端点小于等于 $i$ 的且区间和为 target 的最小区间长度，相当于一个前缀最小值数组。代码中假设数组的下标从 1 开始。
2. 如果区间 [j, i] 的和恰好等于 target，则我们更新答案 i - j + 1 + min_len[j - 1]。同时更新 min_len[i] = min(min_len[i - 1], i - j + 1)。如果小于 target，则只更新 min_len[i] = min_len[i - 1]。初始化 min_len[0] = INF。
3. 由于 $j$ 随着 $i$ 增加单调不减，所以每个位置仅会被遍历两次。

时间复杂度

• 每个位置仅被遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储 min_len 数组。

C++ 代码

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        const int INF = 1000000000;

        int n = arr.size(), ans = INF;
        vector<int> min_len(n + 1);

        min_len[0] = INF;

        int cur = 0;
        for (int i = 1, j = 1; i <= n; i++) {
            cur += arr[i - 1];

            while (j <= i && cur > target) {
                cur -= arr[j - 1];
                j++;
            }

            if (cur == target) {
                ans = min(ans, i - j + 1 + min_len[j - 1]);
                min_len[i] = min(min_len[i - 1], i - j + 1);
            } else {
                min_len[i] = min_len[i - 1];
            }
        }

        if (ans == INF)
            ans = -1;

        return ans;
    }
};