560. 和为 K 的子数组

103 阅读 0 评论 68 点赞

我是靠谱客的博主无限战斗机，这篇文章主要介绍560. 和为 K 的子数组，现在分享给大家，希望可以做个参考。

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：

这道题不会做，看了题解。感觉最关键的就是在于能否想到前缀和这一点，想到的话，这道题几乎就是迎刃而解。

设数组pre来存储nums中的前缀和，即pre[i]代表从nums[0]~nums[i]中所有元素的和。那么，如果某个子数组的和为k，并且以nums[i]结尾，那么这个子数组的起始位置在哪里呢？显而易见，前缀和为pre[i]-k的那个元素，就是子数字的起始位置。

我们在遍历pre数组的时候，一边在hash表中寻找前缀和为 pre[i]-k的元素个数，一边把自己的前缀和加入到hash表中，以便后续的遍历使用。

详细的分析请看题解：

https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/

代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 用hash表来存储某个前缀和出现的次数
        unordered_map<int,int> map;
        int n=nums.size();
        // pre用来存储数组nums的前缀和
        int pre[n];
        // 为pre赋值
        pre[0]=nums[0];
        for(int i=1;i<n;i++)
        pre[i]=pre[i-1]+nums[i];
        // res为最终返回的答案，即和为k的子数组个数
        int res=0;
        // 空数组也是子数组，因此，空数组前缀和为0，存入hash表
        map[0]=1;
        // 遍历pre
        for(int i=0;i<n;i++)
        {
            // 寻找在i之前的某些j，能够满足pre[j]=pre[i]-k
            // 即满足从j+1~i构成的子数组，和为k
            // cha代表pre[i]和k的差值，即pre[j]
            int cha=pre[i]-k;
            // 寻找是否存在这样的j，满足pre[j]=pre[i]-k
            // 存在的话，就意味着能够构成子数组，统计计数
            if(map.find(cha)!=map.end())
            res+=map[cha];
            // 当前的前缀和加入hash表
            map[pre[i]]++;
        }
        return res;
    }
};