LEETCODE 560. Subarray Sum Equals K 解题思路分析

题目大意:

和为K的子数组

给定一个整数数组和一个整数 k,你需要找到该数组中和为 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ,且整数 的范围是 [-1e7, 1e7]。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=560

解题思路分析:

题目要求求出所有连续子数组和为k的个数。看到子数组求和(注意不是子序列),我们应该首先想到presum前缀和的思路,所谓presum,就是求出所有从第0位到当前位的和,比如给定数组为:

nums = [1,3,2]

那么,前缀和用presum数组表示应该为:

presum = [1,4,6]

有了前缀和数组,我们就可以方便的求出任意两位置之间的和,还以上边的nums数组为例,如果想求出index1到index2之间的和,用肉眼可见是5。如果用前缀和来计算的话,公式应该为 presum[j] – presum[i-1],也就是 presum[2] – presum[1-1] = 6 – 1 = 5。

回到本题,要想求出所有和为k的子数组,大概需要以下步骤:

  1. 求出前缀和
  2. 如果当前前缀和等于k,结果加一。
  3. 定义一个记录前缀和的Map,key代表和,value代表该和出现的次数。每计算出一个前缀和,都要更新一下这个Map。
  4. 上文已讲过, presum[j] – presum[i-1] 代表i到j区间的和,因此如果存在 presum[j] – presum[i-1] = k的话,则说明i到j区间是一个结果。换句话说,在当前位置j,如果Map中存在 presum[j] – k这个前缀和的话,说明存在map.get(presum[j] – k)个区间符合结果。可将这个个数加入到结果中。最终,循环完所有前缀和,就能找到所有结果。

完整代码:

public int subarraySum(int[] nums, int k) {
    int res=0; // 定义返回结果
    int sum=0; // 用于计算前缀和
    Map<Integer,Integer> map = new HashMap<>(); // 记录每个前缀和出现的次数
    for(int i = 0; i<nums.length;i++){ // 循环数组
        sum+=nums[i]; // 当前前缀和
        if(sum==k){ // 如果前缀和等于k,结果加一
            res++;
        }
        if(map.containsKey(sum-k)){ // 如果map中存在sum-k
            res += map.get(sum-k); // 将其个数加到结果
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1); // 当前前缀和个数加一存入map
    }
    return res;
}

本解法用时13ms。

Runtime: 13 ms, faster than 94.00% of Java online submissions for Subarray Sum Equals K.

Memory Usage: 38.5 MB, less than 98.91% of Java online submissions for Subarray Sum Equals K.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-560-subarray-sum-equals-k-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

LEETCODE 560. Subarray Sum Equals K 解题思路分析》有1条回应

  1. Pingback引用通告: LEETCODE 1074. Number of Submatrices That Sum to Target解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

邮箱地址不会被公开。