Subarray Sum Equals K

Jin Shang bio photo By Jin Shang

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


  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].


Prefix sum. Rather than keeping the sum, keep a map of count of a certain sum.

Now for any value, we add the number of cnt[sum-k] so the sum would be k.

class Solution {
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int sum = 0;
        int ans = 0;
        cnt[0] = 1;
        for(int i:nums){
            sum += i;
            ans += cnt[sum-k];
        return ans;