祥云县住房和城乡建设局网站,好的手机端网站模板下载安装,基于wordpress的商城系统,做网站的有什么软件560. 和为K的子数组
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例#xff1a; 输入#xff1a;nums [1,1,1], k 2 输出#xff1a;2 法一#xff1a;暴力法
var subar…560. 和为K的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 输入nums [1,1,1], k 2 输出2 法一暴力法
var subarraySum function(nums, k) {let res 0;for(let i0;inums.length;i){let sum 0;for(let j i;j0;j--){sumnums[j];if(sumk){res;}}}return res;
};法二前缀和哈希表
使用前缀和存储累计值利用 currentSum - k 快速找到满足条件的子数组。
function subarraySum(nums, k) {// 初始化前缀和计数器const prefixSumCount new Map();prefixSumCount.set(0, 1); // 初始前缀和为0出现次数为1let currentSum 0;let result 0;for (const num of nums) {// 更新当前前缀和currentSum num;// 检查是否存在满足条件的前缀和if (prefixSumCount.has(currentSum - k)) {result prefixSumCount.get(currentSum - k);}// 更新前缀和计数器prefixSumCount.set(currentSum,(prefixSumCount.get(currentSum) || 0) 1);}return result;
}
