Welcome to Subscribe On Youtube
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
-
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; } } -
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; } }; -
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 -
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 } -
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; }