前缀和的基本概念
题目：560. 和为 K 的子数组
考察S[R]-S[L-1]是否等于k，哈希表的作用可以快速插入一个数、可以快速找到一个数、可以统计数出现的次数。
以下为Java代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int result = 0;
int sum = 0; //表示前缀和
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1); //S[R]-S[L-1] 边界条件
for(int i=0;i<nums.length;i++) {
sum+=nums[i];
if(map.containsKey(sum-k)) {
result += map.get(sum-k);
}
if(map.containsKey(sum)) {
int value = map.get(sum);
map.put(sum,++value);
} else {
map.put(sum, 1);
}
}
return result;
}
}最后
以上就是整齐小白菜最近收集整理的关于前缀和+哈希---leetcode的全部内容，更多相关前缀和+哈希---leetcode内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复