Find Two Non-overlapping Sub-arrays Each With Target Sum LeetCode solution in Java

1
class Solution {
2
  public int minSumOfLengths(
3
      int[] arr, int target) { // this fits the case when there's negative number, kind like 560
4
    if (arr == null || arr.length == 0) return 0;
5
    Map<Integer, Integer> map = new HashMap<>(); // sum - index
6
    map.put(0, -1);
7
    int sum = 0;
8
    for (int i = 0; i < arr.length; i++) { // record preSum and index
9
      sum += arr[i];
10
      map.put(sum, i);
11
    }
12
    sum = 0;
13
    int size = arr.length + 1,
14
        res = arr.length + 1; // note if we set size as MAX_VALUE the line 16 may overflow
15
    for (int i = 0; i < arr.length; i++) {
16
      sum += arr[i];
17
      if (map.containsKey(sum - target))
18
        size =
19
            Math.min(
20
                size,
21
                i
22
                    - map.get(
23
                        sum - target)); // find the subarray from the previous index to current one
24
      if (map.containsKey(sum + target))
25
        res =
26
            Math.min(
27
                res,
28
                size
29
                    + map.get(sum + target)
30
                    - i); // from the current index to next one, this avoid overlap
31
    }
32
    return res == arr.length + 1 ? -1 : res;
33
  }
34
}