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

Link

Solution

 public int minSumOfLengths(int[] arr, int target) {
        int[] bestSoFar = new int[arr.length];
        int sum = 0;
        int start = 0, ans = Integer.MAX_VALUE;
        int curBest = Integer.MAX_VALUE;
        for(int end = 0; end < arr.length; end++){
            sum += arr[end];
            
            while(sum > target){
                sum -= arr[start++];  
            }
            if(sum == target){
                if(start != 0 && bestSoFar[start-1] != 0){
                    ans = Math.min(ans, bestSoFar[start-1] + end - start + 1);
                }
                curBest = Math.min(curBest, end-start+1);
            }
            if(curBest != Integer.MAX_VALUE){
                bestSoFar[end] = curBest;
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }