题目描述
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k
的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
题目解析
这道题的描述很简单,也很好理解,目的就是让我们算出有多少个和为K的连续子数组。
因此最简单的一种方法就是暴力求解,找到所有的子数组,计算和是否为K。
但是,暴力求解虽然简单,但是时间消耗是很大的,时间复杂度是n的平方。所有在数组很大时计算得会很慢。
因此我们可以使用另外一种方式来求解此题,可以思考一下,题目中让求的说连续的子数组和,
这个其实可以转化成用前缀和的方式来表示。例如,求第3到5个数的和,就可以转化为前5个数的和减去前2个数的和,两个前缀和相减就可以来表示一个连续子数组的和。
借助官方题解中的一张图,在遍历结束后,会得到所有的前缀和及其出现的次数,在不断的遍历中pre-k会不断更新,在将其和前缀和去匹配,如果相等了count就加一。
用这种方法,只需遍历一次数组就可以实现,时间会大大减少。
代码如下:
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int pre = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (map.containsKey(pre - k)) {
count += map.get(pre - k);
}
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return count;
}