当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.560.Subarray Sum Equals K 和为K的子数组

LeetCode.560.Subarray Sum Equals K 和为K的子数组

题目描述

560 Subarray Sum Equals K
https://leetcode-cn.com/problems/subarray-sum-equals-k/

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].


相似题目

LeetCode.1248.Count Number of Nice Subarrays 统计优美子数组
LeetCode.560.Subarray Sum Equals K 和为K的子数组
LeetCode.974.Subarray Sums Divisible by K 和可被K整除的子数组
523 连续的子数组和
https://leetcode-cn.com/problems/continuous-subarray-sum/


解题过程

前缀和+哈希Map

本题是 前缀和 方法的经典入门题目。
哈希 Map preSumToCountMap 存储 前缀和 -> 有多少个具有此前缀和的子数组 的映射,以便我们直接在 O(1) 复杂度内找到 前缀和 为 m 的有多少个。
则从前往后遍历数组,每次求出当前的前缀和 preSum,然后找前缀和是 preSum-k 的子数组有多少个,就是当前子数组对最终结果的贡献个数。

时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV202005 {
    public int subarraySum(int[] nums, int k) {
        if (null == nums || nums.length < 1) {
            return 0;
        }
        // 前缀和 -> 有多少个具有此前缀和的子数组
        Map<Long, Integer> preSumToCountMap = new HashMap<>();
        // 暗藏一个前缀和为 0 的子数组
        preSumToCountMap.put(0L, 1);
        int count = 0;
        // 前缀和
        long preSum = 0;
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            // 0... i-1 中有多少个具有前缀和 preSum-k 的子数组,则就有多少个以 i 为结尾的和为 k 的连续子数组
            count += preSumToCountMap.getOrDefault(preSum - k, 0);
            preSumToCountMap.put(preSum, preSumToCountMap.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_560_SubarraySumEqualsK.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_560_SubarraySumEqualsK.java


上一篇 LeetCode.025.Reverse Nodes in k-Group K 个一组翻转链表

下一篇 LeetCode.050.Pow(x,n) 实现Pow(x,n)

阅读
评论
447
阅读预计2分钟
创建日期 2020-05-15
修改日期 2020-05-15
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论