https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/

FindTwoNonOverlappingSubArraysEachWithTargetSum.java

class Solution {
  /** Immutable closed range of array indices */
  private static class IndexRange {
    /** Inclusive start of range */
    public final int start;
    
    /** Inclusive end of range */
    public final int end;
    
    public IndexRange(final int start, final int end) {
      this.start = start;
      this.end = end;
    }
    
    public int length() {
      return end - start + 1;
    }
  }
  
  /** Immutable pair of {code}IndexRange{code}s */
  private static class IndexRangePair {
    public final IndexRange first;
    public final IndexRange second;
    
    public IndexRangePair(final IndexRange first, final IndexRange second) {
      this.first = first;
      this.second = second;
    }
    
    public int length() {
      return first.length() + second.length();
    }
  }
  
  /**
    @returns minimum sum of length of pair of subarrays whose sum is target or -1 if none exist
  */
  public int minSumOfLengths(int[] arr, int target) {
    final var subArrays = subArraysWithSum(arr, target);
    
    return Arrays.stream(subArrays)
      .flatMap(lhs -> {                                   // cross-product
        return Arrays.stream(subArrays)
          .map(rhs -> {
            return new IndexRangePair(lhs, rhs);
          });
      })
      .filter(irp -> {                                    // non-overlapping only
        return irp.first.end < irp.second.start;
      })
      .min(Comparator.comparing(IndexRangePair::length))  // minimum sum of lengths
      .map(IndexRangePair::length)                        // get sum of length
      .orElse(-1);                                        // -1 if non-existent
  }
  
  private IndexRange[] subArraysWithSum(final int[] arr, final int target) {
    final var resultSet = new HashSet<IndexRange>();
    
    int sum = arr[0];
    for (int start = 0, end = 0; start < arr.length && end < arr.length;) {
      int nextSum = sum;
   
      if (sum == target) {
        resultSet.add(new IndexRange(start, end));
      }
      
      if (sum <= target) {
        ++end;
        if (end < arr.length) {
          nextSum += arr[end];
        }
      }
      
      if (sum >= target) {
        if (start < arr.length) {
          nextSum -= arr[start];
        }
        ++start;
      }
      
      sum = nextSum;
    }
    
    return resultSet.stream()
      .sorted((lhs, rhs) -> lhs.length() - rhs.length())
      .toArray(IndexRange[]::new);
  }
}