LeetCode 560. 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

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

Solution

Cumulative-Sum with Hash Table

// Find total pairs of (i, j) such that sum(i, j) = k,
// where sum(i, j) is the cumulative sum 
// from element at index i to element at index j.
// 
// sum(i, j) = k can be transformed into:
// sum(i, j) = k => sum(0, j) - sum(0, i-1) = k
// If we store the cumulative sum from 0 to N-1 into
// another array, then we need to find cusum[j] - cusum[i-1] = k,
// where cusum[x] is the cumulative sum from element at index 0 
// to element at index x.
// 
// Therefore, the problem is pretty similar to two-sum
// that find pairs(i, j) such that nums[i] + nums[j] = k.
// We can apply the similar approach to solve this problem.
//
// In practice, it's not necessary to store all the cumulative sums,
// we can use one variable to update the cumulative sum as we go.
//
// - Define a variable `sum` to store the cumulative sum
// - Intialize a hash map store 
//   (cumulative-sum, number of this cumulative-sum) pairs
// - Iterate all values in the array
//   - Cumulate/Update the sum by current value
//   - If (k - sum) is calculated before
//     - count the number of (k - sum) appears in hash-table
// Time Complexity: O(n)
//   - Iterate all values in the array: O(n)
//     - Find matched sum cumulated before: O(1)
//   => Total: O(n * 1) = O(n)
int subarraySum(vector<int>& nums, int k) {
  int count = 0;
  int sum = 0;
  unordered_map<int, int> sumCounter;
  ++sumCounter[0]; // So we can know sum(0, i) = k or not.
  for (int i = 0 ; i < nums.size() ; ++i) {
    sum += nums[i];
    int target = sum - k;
    auto it = sumCounter.find(target);
    if (it != sumCounter.end()) {
      count += it->second;
    }
    ++sumCounter[sum];
  }
  return count;
}