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 的子数组有多少个，也就是以当前元素为结尾的子树组中和为 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