560. 和为K的子数组

930. 和相同的二元子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

  1. //暴力双指针，从左向右，从值回左，时间On^2，空间O1
  2. func subarraySum(nums []int, k int) int {
  3.     count := 0
  5.     for start := 0; start < len(nums); start++ {
  6.         sum := 0
  8.         for end := start; end >= 0; end-- {
  9.             sum += nums[end]
  10.             if sum == k {
  11.                 count++
  12.             }
  13.         }
  14.     }
  15.     return count
  16. }
  • 每个元素对应一个“前缀和”
  • 遍历数组，根据当前“前缀和”，在 map 中寻找「与之相减 == k」的历史前缀和
  • 当前“前缀和”与历史前缀和，差分出一个子数组，该历史前缀和出现过 c 次，等价于当前项找到 c 个子数组求和等于 k。
  • 遍历过程中，c 不断加给 count，最后返回 count

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组的长度。我们遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为O(n)。

  • 空间复杂度：O(n)，其中 nn 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，因此需要 O(n) 的空间复杂度。

    //前缀和+ 记录哈希键 
func subarraySum(nums []int, k int) int {
  count := 0                  //1,定义出现频次，前缀和，和差值为=k的哈希v-k表
  preSum := 0             
  hash_m := map[int]int{0: 1}        //这句不懂？   用于计算和刚好为k的情况

  for i := 0; i < len(nums); i++ {
      preSum += nums[i]                   //2,前缀和的累加

      if hash_m[preSum - k] > 0 {         //3,若命中，和差值不存在 于哈希表内 【类别两数之和】
          count += hash_m[preSum - k]     //4,则加入哈希表，count=哈希键
      }
      hash_m[preSum] += 1                             //5，若未命中，计算新的累加哈希前缀和
  } 
  return count
}