Leetcode 560.和为K的子数组

题目描述：

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

示例 1：

1
2

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

说明：

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

链接：

https://leetcode-cn.com/problems/subarray-sum-equals-k

题目分析

  刚看到这道题目的时候以为又是经典的滑动窗口问题，小于 k 增大窗口，大于 k 缩小窗口，后来眉头一皱发现事情并不简单，数组中元素可以是负的，那就不能使用滑动窗口了。
  这道题目要寻找数组中某一个区间的和为 k，发现和前几天做的题 Leetcode 437.路径总和 III 道理是完全一样的。那道题中我们把 DFS 遍历的那段路径视为一个数组，然后利用前缀和快速找到和为 target 的区间数量，使用一个哈希表存储前缀和，用前缀和作为 key，数量作为 value。
  对每一个位置的前缀和 sum，寻找前缀和为 sum-k 的个数，那么它们所夹的区间就是和为 k 的区间，将数量添加到结果中即可。然后再更新前缀和哈希表，将当前的前缀和添加进去。需要注意的是，我们需要将前缀和为 0 的数量初始化为 1，表示没有选择数组中任何数时的前缀和为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> preSum;
        preSum[0] = 1;
        int result = 0, sum = 0;
        for(const int& num : nums){
            sum += num;
            if(preSum.find(sum-k) != preSum.end()){
                result += preSum[sum-k];
            }
            preSum[sum]++;
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们只对数组进行了一次遍历，查找哈希表并更新前缀和，而查找和插入哈希表的时间复杂度都是 $O(1)$。
  空间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们需要一个哈希表来存储前缀和，最大的大小就是数组的大小。