【Leetcode HOT100】和为 K 的子数组 c++

题目描述：

给你一个整数数组 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

前缀和+map c++代码：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n=nums.size();
        int s=0;
        unordered_map<int,int> m;//记录从0到i的和 前缀和方法，用unprdered_map防止map给key排序，顺序被打乱,m[i]表示前缀为i的有几个
        m[0]=1; //前缀和为0的情况也存在：第0个元素之前（不包含第0个元素）
        int pre=0;
        for(int i=0;i<n;i++){ //计算m中的值
            pre=pre+nums[i];
            if(m.find(pre-k)!=m.end())s+=m[pre-k]; //每次计算pre后，就以其为子数组尾巴，在之前的所有pre值中查找pre'使得pre-pre'=k
            m[pre]++;
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结：

①前缀法：子数组（连续的称为子数组）之和，可以用前缀和计算。pre[i]表示以i结尾的之前所有元素之和，则pre[i]-pre[j]表示从 i 到 j 的子数组之和。

②map：当需要查找某个值，用map查找比用for循环查找快很多。另外，如果查找顺序要按照给定的顺序查找，则应使用unordered_map，否则map会对key进行从小到大的排序。