跳到主要内容

滑动窗口

· 阅读需 4 分钟
sjktCode

无重复字符的最长子串​

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
var lengthOfLongestSubstring = function (s) {
  const counter = {}
  let ans = 0
  let left = 0

  for (let right in s) {
    counter[s[right]] = (counter[s[right]] || 0) + 1

    while (counter[s[right]] > 1) {
      counter[s[left]] -= 1
      left++
    }

    ans = Math.max(ans, right - left + 1)
  }

  return ans
}

时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符）。

长度最小的子数组​

给定一个含有 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
var minSubArrayLen = function (target, nums) {
  let ans = Infinity
  let sum = 0
  let left = 0

  for (let right in nums) {
    sum += nums[right]

    while (sum >= target) {
      ans = Math.min(ans, right - left + 1)
      sum -= nums[left]
      left++
    }
  }

  return ans <= nums.length ? ans : 0
}

乘积小于 K 的子数组​

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

输入：nums = [1,2,3], k = 0
输出：0
var numSubarrayProductLessThanK = function (nums, k) {
    if (k <= 1) return 0

    let left = 0
    let count = 0
    let product = 1

    for (let right = 0; right < nums.length; right++) {
        product *= nums[right]

        while (product >= k) {
            product /= nums[left]
            left++
        }

        count += right - left + 1
    }

    return count
};

最小覆盖子串​

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
function minWindow(s, t) {
  const charCount = new Map()
  let left = 0,
    minLen = Infinity,
    minWindowStart = 0,
    charsToMatch = t.length

  // 初始化字符计数
  for (const char of t) {
    charCount.set(char, (charCount.get(char) || 0) + 1)
  }

  for (let right = 0; right < s.length; right++) {
    const rightChar = s[right]

    if (charCount.has(rightChar) && charCount.get(rightChar) > 0) {
      charsToMatch--
    }

    charCount.set(rightChar, (charCount.get(rightChar) || 0) - 1)

    // 缩小左窗口
    while (charsToMatch === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1
        minWindowStart = left
      }

      const leftChar = s[left]
      charCount.set(leftChar, (charCount.get(leftChar) || 0) + 1)

      if (charCount.get(leftChar) > 0) {
        charsToMatch++
      }

      left++
    }
  }

  return minLen === Infinity ? '' : s.substr(minWindowStart, minLen)
}
Loading Comments...
0%