2-26 560.和为 K 的子数组

Date：2022-02-27 17:45:52

三个小表情表示题目难度：😄简单 😕中等 😟困难

题目：560.和为 K 的子数组 (😕)

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

说明

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

示例

示例 1

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

 [1,1], [1,1]
 输出: 2

示例 2

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

 [1,2], [3]
 输出：2

分析

该题肯定不能用滑动窗口，因为窗口是固定的，不符合该题

解法有：1暴力法 2前缀和+哈希表优化

题解

1.暴力法，这里采用的正向子串求法，也有反向子串的解法，复杂度都是 O(n^2)

 function main() {
   // const nums = [1, 1, 1]
   const nums = [1, 2, 3]
   const k = 3

   console.log('[]:', subarraySum(nums, k))
 }

 main()

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

   for (let left = 0; left < len; ++left) {
     let sum = 0
     for (let right = left; right < len; ++right) {
       sum += nums[right]

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

       // can not continue, because the next element maybe 0 or negative number
       // continue
       // } else if (sum > k) {
       //   continue
       // }
     }
   }

   return res
 }

2.前缀和法（含哈希优化）

这里最好看视频图解，https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/

但要注意，先判断是否在 map 中，之后再 map.set，因为[j...i-1]

 function subarraySum2(nums: number[], k: number): number {
   let count = 0
   let pre = 0
   const len = nums.length
   const map = new Map<number, number>()

   map.set(pre, 1)

   for (let i = 0; i < len; ++i) {
     pre += nums[i]

     // console.log('[map]:', map)
     // console.log('[pre]:', pre)

     // map's elment is [j...i-1]
     // so it must be ahead of map.set
     let exist0 = map.get(pre - k)
     if (exist0) {
       count += exist0
     }

     // maintain the pre map
     let exist1 = map.get(pre)
     if (exist1) {
       map.set(pre, ++exist1)
     } else {
       map.set(pre, 1)
     }
   }

   return count
 }

扩展 1：滑动窗口算法

一般求解最大和、数组/字符串的子元素问题

示例：给定一个整数数组，计算长度为 'k' 的连续子数组的最大总和。

 输入: [100,200,300,400]

 输出: 700

题解

 function main() {
   const arr = [100, 200, 300, 400, 500, 100]
   const k = 2

   console.log('[]:', maxSum(arr, k))
 }

 main()

 function maxSum(arr: number[], k: number): number {
   let maxSum = 0
   const len = arr.length

   // 边界条件
   if (len < k) return -1

   // 根据窗口大小，初步计算最大值
   for (let i = 0; i < k; ++i) {
     maxSum += arr[i]
   }

   // 挪动窗口，并尝试更新最大值
   for (let i = k; i < len; ++i) {
     const sum = maxSum + arr[i] - arr[i - k]
     maxSum = Math.max(maxSum, sum)
   }

   return maxSum
 }

扩展 2：动态规划算法

关于动态规划，可以参考 [1]

[1] 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？.https://www.zhihu.com/question/23995189

这里上一个简单的示例，题目

给定 1,5,11 三种面值，请给出凑出 15 元的最小组合方式

题解

 function main() {
   const coinFace = [1, 5, 11]
   const w = 15

   console.log('[]:', coinWaysNum(coinFace, w))
 }

 main()

 function coinWaysNum(coinFace: number[], w: number): number {
   const fn = [0]

   for (let i = 1; i <= w; ++i) {
     let cost = Infinity

     for (let j = 0; j < coinFace.length; ++j) {
       if (i - coinFace[j] >= 0) cost = Math.min(cost, fn[i - coinFace[j]] + 1)
     }

     console.log(`[cost${i}]:`, cost)
     fn[i] = cost
   }

   return fn[w]
 }