跳转至

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

来源第 28 场双周赛 Q3难度中等分数1850

题目描述

给你一个整数数组 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\) 的子数组，再两两检查是否重叠并取长度和的最小值。 \(n \le 10^5\)，子数组数量达到平方级，无法通过。

选定右段之后，左段必须完全落在它左侧的前缀里，而且我们只关心那段前缀中最短的合法子数组。这要求我们在扫描过程中随时能回答「前缀里的最短合法段」。

数组元素均为正整数，前缀和严格递增，每个前缀和只对应一个位置。因此用哈希表记下前缀和出现的下标后，就能在常数时间定位以当前位置结尾、和为 \(target\) 的区间 \([j+1,i]\)。

于是从左到右维护 \(f[i]\)：前 \(i\) 个元素中和为 \(target\) 的最短子数组长度。每当找到 \([j+1,i]\)，就用 \(f[j]\) 与当前长度相加更新答案，再令 \(f[i]=\min(f[i-1], i-j)\)。左段始终取自当前段之前，两段自然不重叠。

我们用哈希表 \(d\) 记录每个前缀和出现的位置，初始时 \(d[0]=0\)。

定义 \(f[i]\) 表示数组前 \(i\) 个元素中，和为 \(target\) 的最短子数组的长度。初始时 \(f[0]=\infty\)，答案 \(ans=\infty\)。下标从 \(1\) 开始。

遍历数组 \(\textit{arr}\)。对于当前位置 \(i\)，先令 \(f[i]=f[i-1]\)，并累加得到前缀和 \(s\)。若 \(s-\textit{target}\) 在哈希表中，记 \(j=d[s-\textit{target}]\)，则区间 \([j+1,i]\) 的和为 \(target\)，长度为 \(i-j\)。此时更新 \(f[i]=\min(f[i], i-j)\)，并用左侧最优长度更新答案 \(ans=\min(ans, f[j]+i-j)\)。然后将 \(d[s]\) 记为 \(i\)。

最后，如果 \(ans\) 大于数组长度，则返回 \(-1\)，否则返回 \(ans\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{arr}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        d = {0: 0}
        s, n = 0, len(arr)
        f = [inf] * (n + 1)
        ans = inf
        for i, v in enumerate(arr, 1):
            s += v
            f[i] = f[i - 1]
            if s - target in d:
                j = d[s - target]
                f[i] = min(f[i], i - j)
                ans = min(ans, f[j] + i - j)
            d[s] = i
        return -1 if ans > n else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        Map<Integer, Integer> d = new HashMap<>();
        d.put(0, 0);
        int n = arr.length;
        int[] f = new int[n + 1];
        final int inf = 1 << 30;
        f[0] = inf;
        int s = 0, ans = inf;
        for (int i = 1; i <= n; ++i) {
            int v = arr[i - 1];
            s += v;
            f[i] = f[i - 1];
            if (d.containsKey(s - target)) {
                int j = d.get(s - target);
                f[i] = Math.min(f[i], i - j);
                ans = Math.min(ans, f[j] + i - j);
            }
            d.put(s, i);
        }
        return ans > n ? -1 : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        unordered_map<int, int> d;
        d[0] = 0;
        int s = 0, n = arr.size();
        int f[n + 1];
        const int inf = 1 << 30;
        f[0] = inf;
        int ans = inf;
        for (int i = 1; i <= n; ++i) {
            int v = arr[i - 1];
            s += v;
            f[i] = f[i - 1];
            if (d.count(s - target)) {
                int j = d[s - target];
                f[i] = min(f[i], i - j);
                ans = min(ans, f[j] + i - j);
            }
            d[s] = i;
        }
        return ans > n ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minSumOfLengths(arr []int, target int) int {
    d := map[int]int{0: 0}
    const inf = 1 << 30
    s, n := 0, len(arr)
    f := make([]int, n+1)
    f[0] = inf
    ans := inf
    for i, v := range arr {
        i++
        f[i] = f[i-1]
        s += v
        if j, ok := d[s-target]; ok {
            f[i] = min(f[i], i-j)
            ans = min(ans, f[j]+i-j)
        }
        d[s] = i
    }
    if ans > n {
        return -1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function minSumOfLengths(arr: number[], target: number): number {
    const d = new Map<number, number>();
    d.set(0, 0);
    let s = 0;
    const n = arr.length;
    const f: number[] = Array(n + 1);
    const inf = 1 << 30;
    f[0] = inf;
    let ans = inf;
    for (let i = 1; i <= n; ++i) {
        const v = arr[i - 1];
        s += v;
        f[i] = f[i - 1];
        if (d.has(s - target)) {
            const j = d.get(s - target)!;
            f[i] = Math.min(f[i], i - j);
            ans = Math.min(ans, f[j] + i - j);
        }
        d.set(s, i);
    }
    return ans > n ? -1 : ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
use std::collections::HashMap;

impl Solution {
    pub fn min_sum_of_lengths(arr: Vec<i32>, target: i32) -> i32 {
        let mut d = HashMap::new();
        d.insert(0, 0);
        let n = arr.len();
        let inf = 1 << 30;
        let mut f = vec![0; n + 1];
        f[0] = inf;
        let mut s = 0;
        let mut ans = inf;
        for i in 1..=n {
            s += arr[i - 1];
            f[i] = f[i - 1];
            if let Some(&j) = d.get(&(s - target)) {
                f[i] = f[i].min((i - j) as i32);
                ans = ans.min(f[j] + (i - j) as i32);
            }
            d.insert(s, i);
        }
        if ans > n as i32 {
            -1
        } else {
            ans
        }
    }
}

评论