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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	1 &lt;= arr[i] &lt;= 1000
	1 &lt;= target &lt;= 108


class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        l, windowSum, res = 0, 0, float('inf')
        min_till = [float('inf')] * len(arr) # records smallest lenth of subarry with target sum up till index i.
        for r, num in enumerate(arr): # r:right pointer and index of num in arr
            windowSum += num
            while windowSum > target: 
			# when the sum of current window is larger then target, shrink the left end of the window one by one until windowSum <= target
                windowSum -= arr[l]
                l += 1
			# the case when we found a new target sub-array, i.e. current window
            if windowSum == target:
			   # length of current window
                curLen = r - l + 1
				# min_till[l - 1]: the subarray with min len up till the previous position of left end of the current window: 
				# avoid overlap with cur window
				# new_sum_of_two_subarray = length of current window + the previous min length of target subarray without overlapping
				# , if < res, update res.
                res = min(res, curLen + min_till[l - 1])
				# Everytime we found a target window, update the min_till of current right end of the window, 
				# for future use when sum up to new length of sum_of_two_subarray and update the res.
                min_till[r] = min(curLen, min_till[r - 1])
            else:
			# If windowSum < target: window with current arr[r] as right end does not have any target subarry, 
			# the min_till[r] doesn't get any new minimum update, i.e it equals to previous min_till at index r - 1. 
                min_till[r] = min_till[r - 1]
        return res if res < float('inf') else -1
	
Time = O(n): when sliding the window, left and right pointers traverse the array once.
Space = O(n): we use one additional list min_till[] to record min length of target subarray till index i.
class Solution {
    public int minSumOfLengths(int[] arr, int target) { //this fits the case when there's negative number, kind like 560
        if (arr == null || arr.length == 0) return 0;
        Map<Integer, Integer> map = new HashMap<>(); //sum - index
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < arr.length; i++) { //record preSum and index
            sum += arr[i];
            map.put(sum, i);
        }
        sum = 0;
        int size = arr.length + 1, res = arr.length + 1;//note if we set size as MAX_VALUE the line 16 may overflow
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (map.containsKey(sum - target)) size = Math.min(size, i - map.get(sum - target)); //find the subarray from the previous index to current one
            if (map.containsKey(sum + target)) res = Math.min(res, size + map.get(sum + target) - i); //from the current index to next one, this avoid overlap
        }
        return res == arr.length + 1 ? -1 : res;
    }
}
class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n=arr.size();
        vector<int> prefix(n,INT_MAX);
        vector<int> suffix(n,INT_MAX);
        int sum=0;
        int start=0;
        for(int end=0;end<n;end++){
            sum+=arr[end];
            while(sum>target){
                sum-=arr[start++];
            }
            if(sum==target){
                prefix[end]=min(prefix[end-1>=0 ? end-1 : 0],end-start+1);
            }
            else{
                prefix[end]=prefix[end-1>=0 ? end-1 : 0];
            }
        }

        sum=0;
        start=n-1;
        for(int end=n-1;end>=0;end--){
            sum+=arr[end];
            while(sum>target){
                sum-=arr[start--];
            }
            if(sum==target){
                suffix[end]=min(suffix[end+1<n ? end+1 : n-1],start-end+1);
            }
            else{
                suffix[end]=suffix[end+1<n ? end+1 : n-1];
            }
        }
        int res=INT_MAX;
        for(int i=0;i<n-1;i++){
            if(prefix[i]==INT_MAX || suffix[i+1]==INT_MAX){
                continue;
            }
            res=min(res,prefix[i]+suffix[i+1]);
        }
        return res==INT_MAX ? -1 : res;

    }
};
var minSumOfLengths = function(arr, target) {
    let left=0;
    let curr=0;
    let res=Math.min(); // Math.min() without any args will be Infinite
    const best=new Array(arr.length).fill(Math.min());
    let bestSoFar=Math.min()

    for(let i=0;i<arr.length;i++){
        curr+=arr[i]
        while(curr>target){
            curr-=arr[left++]
        }
        if(curr===target){
            if(left>0&&best[left-1]!==Math.min()){
                res=Math.min(res,best[left-1]+i-left+1)
            }
            bestSoFar=Math.min(bestSoFar,i-left+1)
        }
        best[i]=bestSoFar;
    }
    return res===Math.min()?-1:res
};
Find Two Non-overlapping Sub-arrays Each With Target Sum