图解LeetCode——560. 和为 K 的子数组
一、题目
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k 的连续子数组的个数 。
二、示例
2.1> 示例 1:
【输入】nums = [1,1,1], k = 2 【输出】2
2.2> 示例 2:
【输入】nums = [1,2,3], k = 3 【输出】2
提示:
1
<= nums.length <=2 * 10^4
-1000
<= nums[i] <=1000
-10^7
<= k <=10^7
三、解题思路
根据题目描述,我们要寻找连续的子序列,并且总和等于k的值,然后返回符合以上两个条件的所有子序列个数之和。对于这种与子序列元素统计相关的题目,我们通常第一想法就是通过双层遍历的方式进行计算:
【第1层循环】表示子序列的
起始
位置。 【第2层循环】表示子序列的结束
位置。
但是,这种计算方式时间复杂度较高,我们其实还可以采用前缀和的方式进行计算。什么是前缀和呢?其实就是当我们需要计算集合a[0]、a[1]、a[2]……、a[i]中子序列之和时,有如下规律:
【 计算a[0] 】sum(a[0]) = a[0]; 【 计算a[0]~a[1] 】sum(a[1]) = a[1] + sum(a[0]) ; 【 计算a[0]~a[2] 】sum(a[2]) = a[2] + sum(a[1]) ; 【 计算a[0]~a[i] 】sum(a[i]) = a[i] + sum(a[i-1]) ;
那么假设我们的子序列不是从第一个元素开始的呢?比如要计算a[7]~a[9]
子序列的和。我们可以通过sum(a[9]) -sum(a[6])
来计算。这样做的好处就是,防止重复的遍历和计算。
那么,理解了前缀和之后,我们就可以尝试对这道题进行解答了,解答步骤如下所示:
【步骤1】遍历数组
nums
,并计算下标i对应的前缀和preSum[i]
; 【步骤2】然后用preSum[i]
减去k
值,就是我们还缺少的子序列总和(我们假设是x
); 【步骤3】然后去map
中寻找是否存在key
值是x
的。如果不存在,则说明不匹配;如果存在,则获取到相应的value
值。其中,value值表示子序列总和为key的子序列出现的次数。 【步骤4】将value
值累加到result
上,当所有数组nums
中的元素都遍历完毕之后,result
值就是最终的结果了。
以上就是本题的解题思路了,为了便于理解,我们以输入参数nums=[1,2,3]
,k=3
为例。看一下具体的处理过程是怎么样的,请见下图所示:
四、代码实现
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap();
map.put(0, 1);
int result = 0;
int[] preSum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
preSum[i + 1] = preSum[i] + nums[i];
result += map.getOrDefault(preSum[i + 1] - k, 0);
map.put(preSum[i + 1], map.getOrDefault(preSum[i + 1], 0) + 1);
}
return result;
}
}
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」
转载自:https://juejin.cn/post/7229724099748347963