Subarray Sum Equals K

Description

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

Note:

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

Solutions

My solution

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        // hash[sum]: a list of i such that sum(nums[0..i]) == sum
        unordered_map<int, vector<int>> hash;
        int sum = 0;
        for(int i = 0; i < n; ++i){
            sum += nums[i];
            hash[sum].push_back(i);
        }
        int count = 0;
        // sum(nums[i..j]), 0 <= i <= j < n, dp[j+1] - dp[i]
        sum = 0;
        for(int i = 0; i < n; ++i){
            auto it = hash.find(sum + k);
            if(it != hash.end()){
                for(int j : it->second){
                    if(j >= i)
                        ++count;
                }
            }
            sum += nums[i];
        }
        return count;
    }
};

Optimal solution

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // hash[sum]: number of vectors nums[0..j] such that j < i and sum(nums[0..j]) == sum
        unordered_map<int, int> hash;
        hash[0] = 1;
        int n = nums.size(), sum = 0, count = 0;
        for(int i = 0; i < n; ++i){
            sum += nums[i];
            auto it = hash.find(sum - k);
            if(it != hash.end())
                count += it->second;
            ++hash[sum];
        }
        return count;
    }
};