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

T: O(n)

S: O(n)

class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (map.containsKey(sum - target)) {
                len = Math.min(len, i - map.get(sum - target));
            }
            
            // 左邊一定會先出來, 所以 len != Integer.MAX_VALUE, 不然空有右邊一個, 沒有用
            if (map.containsKey(sum + target) && len != Integer.MAX_VALUE) {
                res = Math.min(res, len + map.get(sum + target) - i);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

/*
0 -1. => 0 -(-1) = 1
3 0
5 1
7 2
11 3  map.get(curSum + target) = get(11+3) = get(14) = 4, 4-i = 4-3 = 1
14 4
            3
    [3,2,2, 4, 3]  target = 3
  0  3 5 7 11 14  
               4
  
         cursum      |
  |--------|---------|--------|
    pre        target  target
    
思路: 預先建構出 presum hashmap

之後 check map.get(sum - target), i - map.get(sum - target)
    
          map.get(sum + target), map.get(sum + target) - i
          
          這樣不會 overlap, 因為當 for (int i = 0; i < n; i++)
          
          我們總是去看 i 之前的, 也就是 sum - target 有沒有 符合的
          和看 i 之後的, 也就是 sum + target 
*/

if arrays contain negative number

T: O(n)

S: O(n)

class Solution {
    public int minSumOfLengths(int[] arr, int target) {          
        int n = arr.length;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        int[] left = new int[n];
        int min = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (map.containsKey(sum - target)) {
                min = Math.min(min, i - map.get(sum - target));
            }
            left[i] = min;
            map.put(sum, i);
        }
        System.out.println("left:"+Arrays.toString(left));
        
        map = new HashMap<>();
        map.put(0, n);
        sum = 0;
        int[] right = new int[n];
        min = Integer.MAX_VALUE;
        for (int i = n-1; i >= 0; i--) {
            sum += arr[i];
            if (map.containsKey(sum - target)) {
                min = Math.min(min, map.get(sum - target) - i);
            }
            right[i] = min;
            map.put(sum, i);
        }
        System.out.println("right:"+Arrays.toString(right));
        
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if (left[i-1] != Integer.MAX_VALUE && right[i] != Integer.MAX_VALUE) {
                res = Math.min(res, left[i-1] + right[i]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

/*
1. left[i] is the size of the min size subarray in arr[0, i] that sums up to target. 
Is Integer.MAX_VALUE if there is no subarray that sums up to target.
2. right[i] is the size of the min size subarray in arr[i, arr.length - 1] that sums up to target.
3. for (int i = 1; i < arr.length; ++i) result = Math.min(result, left[i - 1] + right[i]);

has negative:
  2 -1 0 -1 2 target 1, ans 4
0 2  1. 1  0 2
 
(sum, index)
0 -1
2 0  
1 1   sum - target = 1-1 = 0, 1 -(-1) = 2
1 2
0 3
2 4

from end do prefix sum
  2 -1 0 -1 2 target 1, ans 4
  2  0  1 1 2 0  
 (sum, index)
   0,  arrlen = 5
   
   2   arrlen-1 4
   1   arrlen-2 3 => sum-target = 1 -1 = 0, map.get(0) = 5 - i = 5-3 = 2
   1   arrlen-3 2
   0   arrlen-4 1
   2   arrlen-5 0


ex2:
[3,2,2,4,3]
3

left:[1, 1, 1, 1, 1]
right:[1, 1, 1, 1, 1]

so at last : min(left+right) = 2 

no negative:

0 -1. => 0 -(-1) = 1
3 0
5 1
7 2
11 3  map.get(curSum + target) = get(11+3) = get(14) = 4, 4-i = 4-3 = 1
14 4
            3
    [3,2,2, 4, 3]  target = 3
  0  3 5 7 11 14  
               4
  
         cursum      |
  |--------|---------|--------|
    pre        target  target
    
思路: 預先建構出 presum hashmap

之後 check map.get(sum - target), i - map.get(sum - target)
    
          map.get(sum + target), map.get(sum + target) - i
          
          這樣不會 overlap, 因為當 for (int i = 0; i < n; i++)
          
          我們總是去看 i 之前的, 也就是 sum - target 有沒有 符合的
          和看 i 之後的, 也就是 sum + target 
*/