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 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.


SOLUTION :

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        
        int n = arr.size();
        int i = 0;
        int j = 0;
        
        vector<int> memo(n,INT_MAX);
        
        int len = INT_MAX;
        int res = INT_MAX;
        
        int sum = 0;
        
        while(j < n)
        {
            sum += arr[j];
            
            while(sum > target)
            {
                sum -= arr[i];
                i++;
            }
            
            if(sum == target)
            {
                int window = j-i+1;
                if(i > 0 && memo[i-1] != INT_MAX)
                    res = min(res,window + memo[i-1]);
                
                len = min(len,window);
                
            }
            
            memo[j] = len;
            j++;
        }
        
        if(res == INT_MAX)
            return -1;
        
        return res;
        
    }
};