网站配色的原理和方法,那些市区做网站群,html商城网站源码,做企业画册网站有560.和为K的子数组
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2示例 2#xff1a;
输入#xf…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,看这样的结果是否有被记忆化存储然后累计其次数即可
当然初始时我们设置一个{01}表明默认有一个前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;
};传统节目
