likes
comments
collection
share

图解LeetCode——560. 和为 K 的子数组

作者站长头像
站长
· 阅读数 40

一、题目

给你一个整数数组 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为例。看一下具体的处理过程是怎么样的,请见下图所示:

图解LeetCode——560. 和为 K 的子数组

四、代码实现

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;
    }
}

图解LeetCode——560. 和为 K 的子数组

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

转载自:https://juejin.cn/post/7229724099748347963
评论
请登录