1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

/**

 * 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

 * Given an array of integers arr and an integer target.

 * You have to find two non-overlapping sub-arrays of arr each with 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.

*/

See my solution to the problem here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/FindTwoNonOverlappingSubArraysWithTargetSum.java

The logic is :

1. Create an array ‘best’ in code below to track length of array values equating to sum up to that index. 
2. Iterate from left to right while tracking the sum. 
3. While sum exceeds target, keep dropping values at the leftmost index while incrementing the left index. 
4. At this point sum is less that target or equal to target
5. If sum equals target and the value being tracked at index before current in the ‘best’ array (see #1) is not sentinel, add that value to the current index – left + 1 and update the ans if the new value is less than current.
6. Copy previous best index value to the current index if prior value is less than the new one. 

public int minSumOfLengthsFast(int[] arr, int target) {
    int [] best = new int[arr.length];
    int EDGE = Integer.MAX_VALUE/2;
    Arrays.fill(best, EDGE);
    int sum = 0;
    int left = 0;
    int ans = Integer.MAX_VALUE;
    for (int i =0; i < arr.length; i++) {
        sum += arr[i];
        while (sum > target) {
            sum -= arr[left++];
        }
        if (sum == target) {
            if (left > 0 && best[left - 1] != EDGE) {
                ans = Math.min(ans, best[left - 1] + i - left + 1);
            }
            best[i] = i - left + 1;
        }
        if (i > 0) {
            best[i] = Math.min(best[i - 1], best[i]);
        }
    }
    return (ans > EDGE) ? -1 : ans;
}