国外儿童社区网站模板下载seo公司上海牛巨微

560. 和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例：

输入：nums = [1,1,1], k = 2
输出：2

法一：暴力法

var subarraySum = function(nums, k) {let res = 0;for(let i=0;i<nums.length;i++){let sum = 0;for(let j = i;j>=0;j--){sum+=nums[j];if(sum===k){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;
}