1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
Description
You are given an array of integers arr and an integer target.
You have to find two non-overlapping sub-arrays of arr each with a sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.
Example 1:
Input: arr = [3,2,2,4,3], target = 3 Output: 2 Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.
Example 2:
Input: arr = [7,3,4,7], target = 7 Output: 2 Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.
Example 3:
Input: arr = [4,3,2,6,2,3,4], target = 6 Output: -1 Explanation: We have only one sub-array of sum = 6.
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 10001 <= target <= 108
Solutions
Solution 1: Hash Table + Prefix Sum + Dynamic Programming
We can use a hash table $d$ to record the most recent position where each prefix sum appears, with the initial value $d[0]=0$.
Define $f[i]$ as the minimum length of a subarray with sum equal to $target$ among the first $i$ elements. Initially, $f[0]=\infty$.
Iterate through the array $\textit{arr}$. For the current position $i$, calculate the prefix sum $s$. If $s - \textit{target}$ exists in the hash table, let $j = d[s - \textit{target}]$, then $f[i] = \min(f[i], i - j)$, and the answer is $ans = \min(ans, f[j] + i - j)$. Continue to the next position.
Finally, if the answer is greater than the array length, return $-1$; otherwise, return the answer.
The complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}