和为k的子数组

题目表述

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

示例 1

输入:nums = [1,1,1], k = 2

输出: 2

解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2

输入:nums = [1,2,3], k = 3

输出: 2

提示

1 <= nums.length <= $2\ast {10}^4$

-1000 <= nums[i] <= 1000

$-{10}^7<=k<={10}^7$

解法：前缀和+hash

首先可以通过二重遍历实现所有区间的扫描，这种情况对应时间复杂度$O(n^2)$，为了简化，首先维护一个数组的前缀和preSum数组，对于区间[i,j]的连续和转变为求preSum[i]-preSum[j-1]==k，进一步，在遍历i时，可以维护一个前缀和的 hash 数组preHash用来存放已经遍历过的preSum值，这样向后遍历时仅需判断preSum[i]-k是否存在与 hash 数组中即可（需要判断存在的次数）。

代码实现

from typing import List


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # 前缀和数组: pre_sum[j-1]=pre_sum[i]-k
        count = pre_sum = 0
        count_dict = {0: 1}
        for i in range(len(nums)):
            pre_sum += nums[i]
            if pre_sum - k in count_dict:
                count += count_dict[pre_sum - k]
            count_dict[pre_sum] += 1
        return count

package leetcode

func subarraySum(nums []int, k int) int {
	ans := 0
	for i, _ := range nums {
		cur := 0
		for j := i; j < len(nums); j++ {
			cur += nums[j]
			if k == cur {
				ans += 1
			}
		}
	}
	return ans
}