Subarray Sum Equals K

Problem:

Number of subarrays that Sum to Target

Given an integer array, and a target, return the number of non-empty subarrys that sum to target.

For example, Given array [1, 2, 3] and target 3:
subarray [1, 2] and [3] sum to 3, so the answer is 2.

Solution:

The brutal force solution is to iterate all the indexes, at each position, we iterate all the indexes on the right, calculate the sum and compare with the target. The time complexity is O(N^2) and the space complexity is O(1).

A common pitfall solution is to use sliding window to achieve time complexity O(N) and space complexity O(1) performance. Do you see what's wrong with the following solution?

class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{1, 2, 3};
    int target = 3;
    System.out.println(numOfsubArrays(arr, target));
  }

  /*
  1  2  3
        .
        *
  sum = 3
  count = 2
  */
  public static int numOfsubArrays(int[] arr, int target) {
    int left = 0;
    int n = arr.length;
    int count = 0;
    int sum = 0;
    for(int i = 0; i < arr.length; i++) {
      sum += arr[i];
      if(sum == target)
        count++;
      while(sum > target && left <= i) {
        sum -= arr[left];
        left++;
        if(sum == target)
          count++;
      }
    }
    return count;
  }
}

The code works only if all the elements in the array is positive integer. The above solution is based on the assumption that, when we include a new element in the sliding window, the sum increases, when we remove an old element from the sliding window, the sum decreases. This assumption won't hold if we have negative elements in the subarray.

Actually, if we use a Hashmap to trade space for time, there is a time complexity O(N) and space complexity O(N) solution.

The model is as follows: we iterate from left to right of the array and calculate the sum of elements we saw so far. If we saw a new sum, we put the sum as key and 1 as value to the hashmap. If we saw the same sum later, we increase the value by 1. The reason we build this model is, given any 2 sum[j] and sum[i], the subarray's sum between j and i can be calculated with sum[j] - sum[i]. If the result is equal to k, we found a match.

Now, at each position, we subtract the target from the sum, then use the result as key to look up the hashmap. If we found a match, that means, the current sum minus some previous sum equal to target, which means, the subarray between a previous index and current index sum up to target. We kept saying "some previous sum", how many? It is equal to the value in the hashmap.

import java.util.*;
class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{3, 4, 7, 2, -3, 1, 4, 2};
    int target = 7;
    System.out.println(numOfsubArrays(arr, target));
  }
 
  public static int numOfsubArrays(int[] arr, int target) {
    Map<Integer, Integer> sumCount = new HashMap<>();
    int sum = 0;
    int count = 0;
    for(int i = 0; i < arr.length; i++) {
      sum += arr[i];
      if(sumCount.get(sum - target) != null) {
        count += sumCount.get(sum - target);
      }
      sumCount.put(sum, sumCount.getOrDefault(sum, 1));
    }
    return count;
  }
}

The time complexity is O(N), we need to iterate the array once, the space complexity is O(N), we need a size N hashmap to store the same sum count.