跳到主要内容

1 篇博文 含有标签「滑动窗口」

查看所有标签

力扣209 - 长度最小子数组[滑动窗口]

· 阅读需 4 分钟
Yana Ching
Yana Ching
Front End Engineer

原题描述​

提示

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果 不存在符合条件的子数组，返回 0 。


示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

* 1 <= target <= 109
* 1 <= nums.length <= 105
* 1 <= nums[i] <= 105

滑动窗口解法​

整体的解题思路是

  1. 遍历 t 中所有字符，记录所有字符的出现次数
  2. 判断 left-right 区间内的值是否包含 t 中所有的元素
  3. 如果包含了，判断当前字串与已记录的最小字串，符合更小标准则更新 minL 和 minStart
  4. 在已经包含所有 t 中元素的基础上，移动左指针，移动左指针之前将左指针元素加到原来的哈希表中（不影响，因为不在 t 中元素 在哈希表中查询的结果是 undefined，此时直接加 1，结果就是 NaN，不影响算法结果）

优化点：

  1. 只用了一个哈希表（空间复杂度上减小了）
  2. 每次只更新子串的头节点和长度，仅在最后结果时候做字符串截取
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
function minWindow(s, t) {
  let left = 0
  let right = 0
  let required = t.length
  let minL = Infinity
  let minStart = 0
  const ht = {}
  for (let ct of t) {
    ht[ct] = (ht[ct] || 0) + 1
  }

  let n = s.length
  while (right < n) {
    // right 指针走完 s 的长度为止
    let retR = s[right]
    if (ht[retR] > 0) {
      // 如果是t中元素的话，值为数值，而不是 undefined
      required--
    }
    ht[retR]-- // 无论是否为 t 中元素，直接自减去哈希值 undefined - 1 = NaN
    right++

    while (required === 0) {
      // 判断区间长度是否小于 minL，如果小于则更新 minL、minStart
      if (right - left < minL) {
        minL = right - left
        minStart = left
      }
      // 右移左指针，每次移动都直接增加哈希表中该元素值（undefined + 1 = NaN 不影响算法）
      let retL = s[left]
      ht[retL]++
      // 若是该哈希值大于零，则 left 所指的元素是 t 中值
      if (ht[retL] > 0) required++
      left++
    }
  }
  return minL === Infinity ? '' : s.substring(minStart, minStart + minL)
}