题目
题目
思路
- 暴力：三重循环，超时了
- 去除重复计算：
考虑以i结尾和为k的连续子数组个数，即符合条件的下标j的个数，其中0j
同时，如果我们知道[j, i]子数组的和，就能O(1)推出[j - 1, i]的和。
class solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end >= 0;end--){
sum += nums[end];
if (sum == k) {
count++;
}
}
}
return count;
}
}
- 前缀和 + 哈希表优化
对第二个算法中，需要枚举所有的j处进行优化。
定义pre[i]为[0...i]里所有数的和，则pre[i]可以由pre[i-1]递推而来。那么 [j...i]这个子数组和为k 的这个条件可以转换为
pre[j - 1] == pre[i] - k
即统计有多少个前缀和为pre[i] - k的pre[j]即可。
数据结构：建立哈希表map，以和为key，出现次数为value，记录pre[i]出现的次数。
从左往右遍历，那么以i结尾的答案map[pre[i] - k]即可在O(1)时间内得到。
实现
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
int pre = 0;
Map<Integer, Integer> map = new HashMap<>();
// 空子集
map.put(0,1);
for (int i = 0;i < nums.length;i++) {
pre +=nums[i];
count += map.getOrDefault(pre - k, 0);
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return count;
}
}
