Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

560. Subarray Sum Equals K

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  int subarraySum(vector<int>& nums, int k) {
    int ans = 0;
    int prefix = 0;
    unordered_map<int, int> count{{0, 1}};  // {prefix sum: count}

    for (const int num : nums) {
      prefix += num;
      const int target = prefix - k;
      if (count.count(target))
        ans += count[target];
      ++count[prefix];
    }

    return ans;
  }
};




			


class Solution {
  public int subarraySum(int[] nums, int k) {
    int ans = 0;
    int prefix = 0;
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);

    for (final int num : nums) {
      prefix += num;
      ans += count.getOrDefault(prefix - k, 0);
      count.put(prefix, count.getOrDefault(prefix, 0) + 1);
    }

    return ans;
  }
}




			


class Solution:
  def subarraySum(self, nums: List[int], k: int) -> int:
    ans = 0
    prefix = 0
    count = Counter({0: 1})

    for num in nums:
      prefix += num
      ans += count[prefix - k]
      count[prefix] += 1

    return ans