​

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

目录

一、题目描述

二、测试样例

2.1 测试样例一

2.2 测试样例二

三、算法思路

四、代码实现

五、复杂度分析

5.1 时间复杂度

5.2 空间复杂度

六、总结

前缀和是一个非常巧妙的算法，下面就来看一道题目。

一、题目描述

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

提示：

1 <= nums.length <= 2 * 10^4

-1000 <= nums[i] <= 1000

-10^7 <= k <= 10^7

二、测试样例

2.1 测试样例一

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

输出：2

说明：在输入中，包括两个连续子数组和为 2，它们是 [1, 1] 和 [1, 1]。

2.2 测试样例二

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

输出：2

说明：在输入中，包括两个连续子数组和为 3 ，它们是 [1, 2] 和 [ 3 ]。

三、算法思路

从本题中连续子数组就可以联想到前缀和。遍历整个数组，在遍历过程中不断记录前缀和，使用 map 存储前缀和，那么，只需要查询当前和 sum - k 是否在 map 数组中，在遍历过程中记录和为 k 的连续子数组个数。

四、代码实现

代码实现如下所示：

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

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

int main()
{
    int a[] = {1, 2, 3};
    vector<int>nums(a, a + 3);

    Solution obj;
    cout<<obj.subarraySum(nums, 3)<<endl;
    return 0;
}

​ 图1 通过截图

五、复杂度分析

5.1 时间复杂度

时间复杂度为：O(nlogn)，其中，n 为数组长度，主要的时间复杂度在于 for 循环和 map 数组的查询时间，所以时间复杂度为 O(nlogn)。

5.2 空间复杂度

空间复杂度为：O(n)，在上述算法中，需要使用 map 存储前缀和，所以空间复杂度为 O(n)。

六、总结

本题主要考查前缀和，从题目意思很容易让人联想到前缀和，然后再结合 map 即可解决本题。 

​

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 关注专栏： 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬