题目

给定一个整数数组和一个整数 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 * 104

-1000 <= nums[i] <= 1000

-107 <= k <= 107

注意：本题与主站 560 题相同

解题思路分析

1、暴力法；时间复杂度O(n^2)，空间复杂度O(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 = sum + nums[j]
         if sum == k {
            res++
         }
      }
   }
   return res
}

2、前缀和+遍历；时间复杂度O(n^2)，空间复杂度O(n)

func subarraySum(nums []int, k int) int {
   if len(nums) == 0 {
      return 0
   }
   res := 0
   arr := make([]int, len(nums)+1)
   arr[0] = 0
   for i := 1; i <= len(nums); i++ {
      arr[i] = arr[i-1] + nums[i-1]
   }
   for i := 0; i <= len(nums); i++ {
      for j := 0; j < i; j++ {
         if arr[i]-arr[j] == k {
            res++
         }
      }
   }
   return res
}

3、前缀和+哈希；时间复杂度O(n)，空间复杂度O(n)

func subarraySum(nums []int, k int) int {
   res := 0
   m := make(map[int]int)
   m[0] = 1 // 保证第一个k的存在
   sum := 0
   // sum[i:j]= sum[0:j]-sum[0:i]，把sum[i:j]设为k，
   // 于是可以转化为sum[0:j]-k=sum[0:i]
   for i := 0; i < len(nums); i++ {
      sum = sum + nums[i]
      if _, ok := m[sum-k]; ok {
         res = res + m[sum-k]
      }
      m[sum]++
   }
   return res
}

4、前缀和+哈希；时间复杂度O(n)，空间复杂度O(n)

func subarraySum(nums []int, k int) int {
   res := 0
   m := make(map[int][]int)
   m[0] = []int{-1} // 保证第一个k的存在
   sum := 0
   // sum[i:j]= sum[0:j]-sum[0:i]，把sum[i:j]设为k，
   // 于是可以转化为sum[0:j]-k=sum[0:i]
   for i := 0; i < len(nums); i++ {
      sum = sum + nums[i]
      if _, ok := m[sum-k]; ok {
         res = res + len(m[sum-k])
         // 输出满足条件的子数组下标
         // for _, v := range m[sum-k] {
         // fmt.Println(v+1, i)
         // }
      }
      m[sum] = append(m[sum], i)
   }
   return res
}

总结

Medium题目，题目同
leetcode 560.和为K的子数组
leetcode 1546.和为目标值的最大数目不重叠非空子数组数目