题意：给定一个数组，找出所有和为k的子数组的个数
思路：
- 遍历数组，用hashmap记录所有之前出现过的值的和，以及它们出现的个数
- 每次查看map中是否有sum-k的key，如果有把它对应的出现个数加入结果
- 把<0，1>放入hashmap中，用来计算sum==k本身的情况
思想：hashmap
复杂度：时间O（n)，空间O(n)
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap();
int sum = 0;
map.put(0, 1);
int res = 0;
for(int i=0;i<nums.length;i++) {
sum += nums[i];
res += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return res;
}
}
网友评论