我需要知道关于前缀和的问题。
我需要知道关于前缀和的问题。
提问于 2022-10-10 19:03:27
var subarraySum = function(nums, k) {
let obj = {
0: 1
};
let count = 0;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
if (obj[sum - k]) {
count += obj[sum - k];
}
obj[sum] = ++obj[sum] || 1;
}
return count;
};
console.log(subarraySum([1, 2, 3, 3, 2, 1, 3], 4))
console.log(subarraySum([1, 2, 3, 3, 2, 1, 3], 5))
问题陈述:给定整数、num和整数k的数组，返回和等于k的子数组的总数。子数组是数组中连续的、非空的元素序列。
为什么我们将obj定义为{0 : 1}？当你写objsum-k的时候到底发生了什么？
回答 1
Stack Overflow用户
发布于 2022-10-10 19:50:27
代码中有更多的注释。首先，我简化了一些意在混淆的语句。那么我们就剩下纯算法了。我们的想法是保持一个total和我们到目前为止“见过”的所有总数。如果在任何一点上我们发现当前的总计“在前面看到”+ k，这意味着我们找到了一个总k子组
var subarraySum = function(nums, k) {
// obj counts true or false for *every* sum we accomulate
let obj = {
0: 1
};
let count = 0;
let sum = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i];
// if we encounter a seen before difference between sum and k
// it means we have a "sum-k subgroup" thus far.
// example:
// consider we encounterd 1, 2, 3, 4 so we encounterd 10, right?
// we keep going then we a point of sum 15
// it means we must have since the last 10 found a subgroup of sum 5
if (obj[sum - k]) {
// so we found one
count++
}
// mark current sum as encountered = true
obj[sum] = 1;
}
return count;
};
console.log(subarraySum([1, 2, 3, 3, 2, 2, 1, 3], 5)).as-console-wrapper {
max-height: 100% !important
}
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74019638
复制相关文章
相似问题
腾讯云开发者
