LeetCode 560. 和为 K 的子数组

LeetCode 560. 和为 K 的子数组

  

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

思路：

• 双层循环暴力求解
• 前缀和，利用空间换时间的思想，参考 LeetCode 大佬题解

  
  思路类似于【LeetCode 1. 两数之和】。遍历 nums 数组，求每一项的前缀和，并统计对应nums[i]的出现次数，以键值对存入 map。注意 初始边界值：开始时0个元素和为0，所以将 0:1 存入map。

  边存边检查 map，如果 map 中存在 key 为「当前前缀和 - k」，说明这个之前出现的前缀和，满足「当前i所对应的前缀和 - 之前出现的前缀和 == k」。最后，将「当前前缀和 - k」出现的次数，累加到结果中即可。
  
  通俗的说，已知当前 i 所对应的前缀和为 prefixSum[i]，我们想找出 prefixSum[i] 减去之前的某些连续子数组和之后的差值等于k的这么一些连续子数组，那么满足条件：当前 i 所对应的前缀和 prefixSum[i] - 之前出现的前缀和 x = k，那么这个 x = prefixSum[i] - k，接下来我们要判断这个 x 在之前是否出现过，因此将求得的每一项前缀和，以及对应的出现次数，以键值对形式存入 map中，以便后续判断。

注意：nums中可能存在负数，sum累加和可能更大也可能更小，因此，即使累加和等于k，也不能提前break退出

时间复杂度：

• 双层循环暴力求解：O(n^2)
• 利用前缀和：O(n)

空间复杂度：

• 双层循环暴力求解：O(1)
• 利用前缀和：O(n)

// 方法1 双层循环暴力求解
func subarraySum(nums []int, k int) int {
    res := 0

	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
            sum += nums[j]
            if sum == k {
                res++
                // break // nums中可能存在负数，sum累加和可能更大也可能更小，不能提前break退出
            }
		}
	}

	return res
}

// 方法2 前缀和（推荐）
// 参考：https://leetcode.cn/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/
// 思路：类似于【1、两数之和】，遍历 nums 数组，求每一项的前缀和，统计对应的出现次数，以键值对存入 map。
// 边存边检查 map，如果 map 中存在 key 为「当前前缀和 - k」，说明这个之前出现的前缀和，满足「当前前缀和 - 该前缀和 == k」，它出现的次数，累加给 count
func subarraySum(nums []int, k int) int {
    m := map[int]int{0:1}
    sum, res := 0, 0

    for i := 0; i < len(nums); i++ {
        sum += nums[i]
        if cnt, ok := m[sum - k]; ok {
            res += cnt
        }
        m[sum] += 1
    }

    return res
}