Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:
nums = [1,1,1], k = 2

Output:
 2

Note:

1. The length of the array is in range [1, 20,000].

2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Analysis

Approach 1 - Cumulative sum without space

Instead of considering all the startstart and endend points and then finding the sum for each subarray corresponding to those points, we can directly find the sum on the go while considering different endend points.

Whenever the sumsum equals the required kk value, we can update the countcount value

if (sum == k) count++;

Approach 2 - Prefix Sum + Hash Table

If the cumulative sum(repreesnted by sum[i] for sum upto i-th index) upto two indices is the same, the sum of the elements lying in between those indices is zero.

sum[i] is prefix sum till i-th element

if sum[j] − sum[i - 1] = k, then update count.

Thus, storing prefix sum in hashmap, if (sum - k) found, then it means, we found a subarray with sum k.

Also, the hashmap keeps the count for the frequencies of the prefix sum (sum i, No. of occurences of sum i), so that it could add together to the total count of the subarray with sum k.

Note: a tricky part is to initialize the hashmap with map.put(0, 1);

Since actually the sum as hashmap key stored is sum[0, j]

and sum[i, j] = sum[0, j] - sum[0, i - 1], therefore if the sum[0, j] itself is k, then we are checking if the map contains 0

as key, so we have map.put(0, 1); to make sure the count will add one when it find sum - k == 0

Some explanation from discussion @y495711146:

/*
1. Hashmap<sum[0,i - 1], frequency>
2. sum[i, j] = sum[0, j] - sum[0, i - 1]    --> sum[0, i - 1] = sum[0, j] - sum[i, j]
       k           sum      hashmap-key     -->  hashmap-key  =  sum - k
3. now, we have k and sum.  
      As long as we can find a sum[0, i - 1], we then get a valid subarray
     which is as long as we have the hashmap-key,  we then get a valid subarray
4. Why don't map.put(sum[0, i - 1], 1) every time ?
      if all numbers are positive, this is fine
      if there exists negative number, there could be preSum frequency > 1
*/

https://leetcode.com/problems/subarray-sum-equals-k/discuss/102106/Java-Solution-PreSum-%2B-HashMap

Another way (straight-forward, preferred) of implementing it is just do a check outside of the hashmap containsKey(),

if (sum == k) {
    count++;
}

in this way, we don't need to initialize hashmap with (0, 1).

See https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/

Solution

Cumulative sum - O(n^2) time, O(1) space (218 ms)

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) {
            int sum=0;
            for (int end = start; end < nums.length; end++) {
                sum+=nums[end];
                if (sum == k)
                    count++;
            }
        }
        return count;
    }
}

Prefix Sum + Hash Table - O(n) time, O(n) space (37ms beats 40.49%)

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;

    }
}

Another implementation - Prefix Sum + Hash Table - O(n) time, O(n)

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) {
                count++;
            }
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;

    }
}