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
解
暴力方法就不多说了,二重循环解决。
我说一下时间复杂度为O(n)的算法:
其实我们求这个所谓的子数组k,肯定累计计算前n项和,每次我们记忆化存储前n项和,键为前n项目和,值为对应该和出现的次数
满足子数列和为k翻译一下就是,总结前n项和减去k,看这样的结果是否有被记忆化存储,然后累计其次数即可,
当然,初始时我们设置一个{0,1},表明默认有一个前n项和为0的情况
参考代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
const map = new Map();
map.set(0, 1);
let count = 0, pre = 0;
for(const x of nums) {
pre += x;
if(map.has(pre - k))
count+= map.get(pre - k)
if(map.has(pre))
map.set(pre, map.get(pre) + 1);
else
map.set(pre, 1);
}
return count;
};