What is the main strategy to solve Find Two Non-overlapping Sub-arrays Each With Target Sum?

Use a prefix sum hash map to locate sub-arrays efficiently, then combine minimal left and right lengths to find non-overlapping pairs.

How do prefix and suffix arrays help in this problem?

Prefix and suffix arrays store minimal lengths of sub-arrays from the left and right, allowing quick combination checks without overlap.

Can the array contain negative numbers?

Yes, but prefix sum tracking must account for decreasing sums, which may require extra care in hash map updates.

What should be returned if only one valid sub-array exists?

Return -1 because the problem requires exactly two non-overlapping sub-arrays.

Is this problem solved using sliding window?

Sliding window works only for positive integers; for mixed or general cases, hash map prefix sums ensure correctness.

#1477

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个整数数组 arr 和一个整数值 target 。请你在 arr 中找两个互不重叠的子数组且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的最小值。请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。示例 1：输入： …

数组哈希表二分查找动态规划滑动窗口

题目描述

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

lightbulb

解题思路

方法一：哈希表 + 前缀和 + 动态规划

我们可以使用哈希表 $d$ 记录前缀和最近一次出现的位置，初始时 $d[0]=0$ 。

定义 $f[i]$ 表示前 $i$ 个元素中，长度和为 $target$ 的最短子数组的长度。初始时 $f[0]= \infty$ 。

遍历数组 $\textit{arr}$ ，对于当前位置 $i$ ，计算前缀和 $s$ ，如果 $s - \textit{target}$ 在哈希表中，记 $j=d[s - \textit{target}]$ ，则 $f[i]=\min(f[i], i - j)$ ，答案为 $ans=\min(ans, f[j] + i - j)$ 。继续遍历下个位置。

最后，如果答案大于数组长度，则返回 $-1$ ，否则返回答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is scanned once and hash map lookups are O(1). Space complexity is O(n) for the prefix and suffix arrays plus the hash map.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for multiple sub-arrays with the same sum and ensure non-overlapping selection.
question_mark
Expect discussion on using prefix sums with hash maps to quickly identify valid sub-arrays.
question_mark
Watch for edge cases where no two valid sub-arrays exist, requiring a -1 return.

warning

常见陷阱

外企场景

error
Overlapping sub-arrays are mistakenly counted; always verify index boundaries.
error
Not updating the minimal length in prefix or suffix arrays, leading to incorrect total length.
error
Ignoring single sub-array cases where a second sub-array does not exist.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find k non-overlapping sub-arrays with the same target sum and minimize total length.
arrow_right_alt
Return the maximal total length of two non-overlapping sub-arrays with target sum.
arrow_right_alt
Handle arrays with negative integers, requiring careful prefix sum handling.

help

常见问题

外企场景

继续练习

#1658 将 x 减到 0 的最小操作数 #1027 最长等差数列 #2008 出租车的最大盈利