JAVA 牛牛

560. 和为K的子数组

  • May 15, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： 前缀和 哈希表
  • 思路： 前缀和 哈希表
  • 类似题型:

题目 560. 和为K的子数组

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

示例 1 :

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

说明 :

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

方法一 前缀和

解题思路

  • 题目理解：
    • 在数组 nums 中找到连续子数组和为 k，并返回子数组个数
    • 我们假设 从左到右 前缀和为 preSum[0]preSum[0]...preSum[i+1]
    • 我们再根据下面的 前缀和推倒过程 ，可以得到任意连续子数组和
    • 只要 $preSum[right+1] - preSum[left] = k$ 即可得到结果
  • 前缀和推倒过程： 
    preSum[0] = 0
preSum[1] = num[0] = preSum[0] + nums[0]
preSum[2] = num[0] + num[1] = preSum[1] + nums[1]
preSum[3] = num[0] + num[1] + nums[2] = preSum[2] + nums[2]
.
.
preSum[i+1] = num[0] + num[1] ... + nums[i] = preSum[i] + nums[i]
  • 复杂度分析：
    • 时间复杂度 $O(N^2)$ ：假设数组长度为 n ，遍历两次 ；
    • 空间复杂度 $O(N+1)$ ：假设数组长度为 n，其中 preSum[0] 为前缀初始值。

java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        // 计算前缀和数组
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int count = 0;
        for (int left = 0; left < len; left++) {
            for (int right = left; right < len; right++) {
                // 区间和 [left..right]，注意下标偏移
                if (preSum[right + 1] - preSum[left] == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        nums_len = len(nums)
        pre_sum = [0] * (nums_len+1)
        count = 0
        for i,num in enumerate(nums):
            pre_sum[i+1] = pre_sum[i] + num
        for left in range(len(nums)):
            for right in range(left,len(nums)):
                if pre_sum[right+1] - pre_sum[left] == k:
                    count += 1
        return count

方法二 前缀和 + 哈希表

  • 还是前缀和的思想，我们把前缀和放在 map 中， map.put(preSum,前缀和出现次数) (数组中可能会有负数，所以可能会重复出现)

java

public int subarraySum(int[] nums, int k) {
        int count = 0;
        // key:前i个元素的和，value：对应key 出现的个数
        Map<Integer,Integer> preSumMap = new HashMap<>();
        // 数组下标为 0，则前面数组为空，所以和为 0，且出现一次  
        preSumMap.put(0, 1);
        int preSum = 0;
        for(int i = 0;i<nums.length;i++) {
            preSum += nums[i];
            if (preSumMap.containsKey(preSum-k)){
                count += preSumMap.get(preSum-k);
            }
            preSumMap.put(preSum, preSumMap.getOrDefault(nums[i], 0)+1);
        }

        return count;
    }

python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        pre_sum = 0
        count = 0
        pre_sum_dict = collections.defaultdict(int)
        pre_sum_dict[0] = 1
        for num in nums:
            pre_sum += num
            if pre_sum - k in pre_sum_dict:
                count += pre_sum_dict.get(pre_sum - k)
            pre_sum_dict[pre_sum] +=  1
        return count
  • 复杂度分析：
    • 时间复杂度 $O(N)$ ：假设数组长度为 n ，我们遍历数组长度为 n
    • 空间复杂度 $O(N)$ ：假设数组长度为 n，哈希表在最坏的情况下，保存 n 个不同元素
  • 如果你觉得本文对你有帮助，请点赞👍支持
  • 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出
Search