Find Two Non-overlapping Sub-arrays Each With Target Sum
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 to 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 = 3Output
2Only two sub-arrays have sum = 3 ([3] and [3]), and the sum of their lengths is 2.
Example 2
Input
arr = [7,3,4,7], target = 7Output
2Although there are three non-overlapping sub-arrays of sum = 7 ([7], [3,4], and [7]), choosing the first and third gives the minimum total length of 2.
Constraints
- 1 <= arr.length <= 10^5
- 1 <= arr[i] <= 1000
- 1 <= target <= 10^8