560. 和为K的子数组 力扣（中等） 字节面试题，不会，前缀和，hash，有尺取法的味道

题目描述：

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

示例 1 :

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

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

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

题解：思考的辛酸史，一上来，尺取法，发现k<0，不可以，数据量2w，非常大，放弃。。。

不用求出 prefixSum 数组
其实我们不关心具体是哪两项的前缀和之差等于k，只关心等于 k 的前缀和之差出现的次数c，就知道了有c个子数组求和等于k。
遍历 nums 之前，我们让 -1 情况下的前缀和为 0，这样通式在边界情况也成立。即在遍历之前，map 初始放入 0:1 键值对。
遍历 nums 数组，求每一项的前缀和，统计对应的出现次数，键值对方式存入 map。
边存边查看 map，如果 map 中存在：键值 =当前前缀和-k，说明这个之前出现的前缀和，满足「当前前缀和 - 该前缀和 == k」，它出现的次数，累加给 count。

求个数，不需要，头尾坐标

怀疑和尺取法有异曲同工之妙，打算用这个方法去试试，

1838. 最高频元素的频数，对应题解

代码：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
    int l=nums.size();
    int res=0;
    map<long long, int> mp;
    mp[0]=1;  // 当没有取任何数时，前缀和为0，出现1次
    long long sum=0;
    for(auto i: nums)
    {
        sum+=i;
        if(mp.find(sum-k)!=mp.end()) res+=mp[sum-k];   //是否存在和当前和差k的前缀和存在
        mp[sum]++;
    }
         return res;
    }
};

560. 和为K的子数组 力扣（中等） 字节面试题，不会，前缀和，hash，有尺取法的味道

原文：https://www.cnblogs.com/stepping/p/15073239.html