LC560 - Subarray Sum Equals K

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals tok.

A subarray is a contiguous non-empty sequence of elements within an array.

Example

Example 1:

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

Output: 2

Example 2:

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

Output: 2

Solution

Use a hash map to keep track of prefix sums as we iterate through the array. This allows us to process the entire array in T(O(n)) and S(O(n)).

int subarraySum(vector<int>& nums, int k) {
	unordered_map<int, int> prefixSums;
	prefixSums[0] = 1;
	
	auto sum = 0;
	auto count = 0;
	
	for (auto num : nums) {
		sum += num;
		
		// Check if prefix sum exists such that delta(cSum, pSum) ==k
		if (prefixSums.find(sum - k) != prefixSums.end()) {
			count += prefixSums[sum - k];
		}
		
		prefixSums[sum]++;
	}
	
	return count;
}