#和为 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

#解题思路

题目信息：连续，nums[i]可以为负数

#思路一

暴力解法，双层循环，复杂度 O(n2)

#思路二

因为 nums[i]可能为负数，所以不能用滑动窗口调整窗口内和的大小来匹配 k

只能用前缀和与哈希来讲问题转换为求前缀和的差值为 k sum(i,j)=sum(0,j)-sum(0,i)

#首次代码

function subarraySum(nums: number[], k: number): number {
  let res = 0

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === k) {
      res++
    }

    let sum = nums[i]

    for (let j = i + 1; j < nums.length; j++) {
      sum += nums[j]

      if (sum === k) {
        res++
      }
    }
  }

  return res
}

#优化代码

function subarraySum(nums: number[], k: number): number {
  const map: Record<number, number> = { 0: 1 }
  let prefixSum = 0
  let res = 0

  for (let i = 0; i < nums.length; i++) {
    prefixSum += nums[i]

    if (map[prefixSum - k]) {
      res += map[prefixSum - k]
    }

    map[prefixSum] = map[prefixSum] ? map[prefixSum] + 1 : 1
  }

  return res
}