The pattern is about combining cumulative sum in two different points of time(array pointers) and making assumptions about their differences.

We usually count occurunces of particular sum in hashmap, then adding those counts to result.

Example

Subarray Sum Equals K

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> preSum = new HashMap<>();
    preSum.put(0, 1); **// we've seen sum 0 - once**
    int sum = 0, count = 0;
    for(int i = 0; i < nums.length; i++) {
        sum += nums[i];
	**// if exsists sum - k, that means sum between those two points in array = k**
        if (preSum.containsKey(sum - k)) {
            count += preSum.get(sum - k);
        }
        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
    }
    return count;
}

We can say that if we have sum = A in any index of array AND we've alredy seen sum = A - K then subarray sum between two points is equal to K.

Example 2

Trick when we build not accumulated sum of all numbers, but their dividers etc.

public int numberOfSubarraysPrefix(int[] arr, int k) {
    if (k == 0) return 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1); // we've seen sum 0 once
    int sum = 0, res = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i] % 2 == 0 ? 0 : 1;
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        res += map.getOrDefault(sum - k, 0);
    }
    return res;
}

OR

public int numOfSubarrays(int[] arr) {     
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    map.put(1, 0);
    int sum = 0, result = 0;
    for(int i = 0; i < arr.length; i++) {
        sum = (sum + arr[i]) % 2;
        int abs = Math.abs(sum - 1);
        if (map.containsKey(abs)) {
            result += (map.get(abs));
        }
        map.put(sum, (map.get(sum) + 1));
    }
    return result;
}

Untitled

Complexities

We're looking for O(N) time and O(N) or O(1) space.