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

题目大意：

和为K的子数组

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

示例 1 :

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

说明 :

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-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-解题思路分析/