LeetCode 1477: Find Two Non-overlapping Sub-arrays Each With Target Sum
Problem Description
Explanation:
To solve this problem, we can use a two-pointer technique combined with prefix sums. We iterate through the array and calculate the prefix sum at each index. Then, we iterate through the array again and for each index, we find the length of the subarray with sum equal to the target from the left end. We store these lengths in an array.
Next, we iterate through the array in reverse and for each index, we find the length of the subarray with sum equal to the target from the right end. We store these lengths in another array.
Finally, we iterate through both arrays and find the minimum sum of lengths of the two non-overlapping subarrays with the target sum.
:
Solutions
class Solution {
public int minSumOfLengths(int[] arr, int target) {
int n = arr.length;
int[] leftSum = new int[n];
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0, minLen = Integer.MAX_VALUE, result = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
sum += arr[i];
leftSum[i] = minLen;
if (map.containsKey(sum - target)) {
int len = i - map.get(sum - target);
minLen = Math.min(minLen, len);
}
map.put(sum, i);
}
map.clear();
map.put(0, n);
sum = 0;
for (int i = n - 1; i >= 0; i--) {
sum += arr[i];
if (map.containsKey(sum - target)) {
int len = map.get(sum - target) - i;
if (len + leftSum[i] < result) {
result = len + leftSum[i];
}
}
if (i > 0) {
map.put(sum, i);
}
}
return result == Integer.MAX_VALUE ? -1 : result;
}
}Loading editor...