图解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^)/ ~ 「干货分享,每天更新」

相关文章
|
6月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
3月前
|
算法 Python
【Leetcode刷题Python】子数组查找
一个用于寻找给定字符串中最长重复子串的Python函数实现,采用了滑动窗口的方法来检测重复的子串。
20 1
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
43 0
|
5月前
|
算法 测试技术 程序员
力扣经典150题第三十题:长度最小的子数组
力扣经典150题第三十题:长度最小的子数组
29 1
|
4月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
技术经验解读:【LeetCode】560.SubarraySumEqualsK子数组和为K
技术经验解读:【LeetCode】560.SubarraySumEqualsK子数组和为K
|
5月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
6月前
【力扣】209. 长度最小的子数组
【力扣】209. 长度最小的子数组
|
6月前
|
算法 测试技术
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
|
6月前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
40 0