前缀和
二维前缀和思路
前缀和的关键思路就是通过从 i 开始的一个总和从 j 开始另一个总和的差值,表示 i 到 j 这段距离的值。
例:子数组nums[i:j]
(包含从 i 到 j 的元素)的和可以通过前缀和 prefixSum[j] - prefixSum[i - 1]
来表示,其中 prefixSum[i]
表示从 0 到 i 的元素总和。
例题
560. 和为 K 的子数组
方法:暴力解法
时间复杂度:O(n^2)
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let ans = 0;
const len = nums.length;
for(let i = 0 ; i < len ; i ++) {
let cur = nums[i];
if (cur === k) ans ++;
let j = i + 1;
while (j < len) {
cur += nums[j];
if (cur === k) {
ans ++;
}
j ++;
}
}
return ans;
};
前缀和
时间复杂度:O(n)
思路:
-
初始化一个哈希表
prefixSums
来存储前缀和及其出现的次数。 -
遍历数组
nums
,计算从开始到当前位置的连续元素和,即前缀和sum
。 -
对于每个前缀和
sum
,我们检查prefixSums
中是否存在sum - k
。如果存在,这意味着从数组的某个位置到当前位置的子数组和为 k,我们将该前缀和出现的次数加到count
上。 -
更新
prefixSums
,将当前的前缀和sum
的出现次数增加 1。如果sum
之前没有出现过,就将其加入哈希表并设置次数为 1。 -
继续遍历直到数组结束,最后返回
count
。
思考:为什么判断 sum - k
?
答:sum - prefixSums[x] = k
-> prefixSums[x] = sum - x
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function(nums, k) {
let count = 0;
let sum = 0;
let prefixSums = new Map();
prefixSums.set(0, 1); // 初始化前缀和为0的计数为1
for (let i = 0; i < nums.length; i++) {
sum += nums[i]; // 计算当前前缀和
// 如果之前有前缀和等于当前前缀和减去k,那么在之前的前缀和和当前位置之间就是一个和为k的子数组
if (prefixSums.has(sum - k)) {
count += prefixSums.get(sum - k);
}
// 更新当前前缀和的计数
prefixSums.set(sum, (prefixSums.get(sum) || 0) + 1);
}
return count;
};