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

题解思路

我们先要理解前缀和的概念。
对于一个数组a[n]，我们定义前缀和

s[0] = a[0]
s[1] = a[0] + a[1] = s[0] + a[1]
s[2] = a[0] + a[1] + a[2] = s[1] + a[2]
......
s[n] = a[0] + a[1] + … + a[n] = s[n - 1] + a[n]

那么，对于子数组a[l, r]，其和

sum[l, r] = a[l] + … + a[r] = s[r] - s[l - 1]

对于本题，如果我们假设sum[j, i]为以子数组a[j, i]的和，那么对于j属于[0, i)，子数组的和为k，即

sum[j, i] = s[i] - s[j - 1] = k

相当于，

s[j - 1] = s[i] - k

我们要求解的就是s[j - 1]的个数，这个可以用一个hash表(unordered_map[HTML_REMOVED]，key为前缀和，value为个数)来统计。特别的，由于j的下标从0开始，我们要定义

s[0 - 1] = s[-1] = 0

即hash中，前缀和等于0(即s[-1] = 0)的个数已经有1个，我们需要初始化hash[0] = 1

code

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0;
        unordered_map<int, int> hash;
        hash[0] = 1;

        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            res += hash[sum - k];
            ++hash[sum];
        }

        return res;        
    }
};