题目描述

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

样例

输入: nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

算法

(前缀和+哈希) $O(n)$

本题与 LeetCode 930. Binary Subarrays With Sum 类似，我们可以枚举区间的终点，用哈希表来记录终点前的前缀和出现次数，以当前点为终点的和为k的子数组的出现次数即为当前前缀和减去k后的前缀和的次数。

这里要注意初始化时前缀和为0的数组出现次数设置为1，用来计算当前前缀和恰好为k的情况。另外由于数组中有负数存在，所以本题不存在单调性，不能用双指针来做。

C++ 代码

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

        for (int i = 0, sum = 0; i < A.size(); i ++ ) {
            sum += A[i];
            if (hash.count(sum - S)) res += hash[sum - S];
            hash[sum] ++ ;
        }

        return res;
    }
};