介绍

滑窗技术是一种计算技术，其目的是减少嵌套循环的使用，用单个循环代替，从而降低时间复杂性。

什么是滑窗？考虑一条连接在一起的长链。假设你想用你的手在整条链条上涂油，而不从上面倒油。一种方法是：将一些油涂抹在链条的一个部分，然后再次将一些油涂在下一个尚未涂油的部分，以此类推，直到整条链条都上了油。另一种方法是用一块布，蘸上油，然后用这块布抓住链条的一端。然后不用再重复蘸油，只需用手将布滑到下一节，再下一节，以此类推，直到另一端。

第二种方法被称为滑动窗口技术，从一端滑动到另一端的部分，被称为滑动窗口（Sliding Window）。

使用滑动窗口技术的先决条件：

滑动窗口技术的使用可以在一个非常特殊的情况下进行，在整个嵌套循环中，计算窗口的大小是固定的。只有这样才能降低时间的复杂性。

如何使用滑动窗口技术？

滑动窗口技术的一般使用方法可以演示如下：

• 找到所需的窗口大小。
• 从数据结构的开始计算第一个窗口的结果。
• 然后用一个循环来滑动窗口，并继续逐窗计算结果。

案例

最长不重复子串

获取不含重复字符的最长子串的长度。

/**
 * @function LongestSubstringWithoutRepeatingCharacters
 * @description Get the length of the longest substring without repeating characters
 * @param {String} s - The input string
 */
function LongestSubstringWithoutRepeatingCharacters (s) {
  let maxLength = 0
  let start = 0
  let end = 0
  const map = {}
  while (end < s.length) {
    if (map[s[end]] === undefined) {
      map[s[end]] = 1
      maxLength = Math.max(maxLength, end - start + 1)
      end++
    } else {
      while (s[start] !== s[end]) {
        delete map[s[start]]
        start++
      }
      delete map[s[start]]
      start++
    }
  }
  return maxLength
}

是否包含排列

给定两个字符串 s1 和 s2，如果 s2 包含 s1 的排列，则返回真，否则返回假。

/**
 * @function PermutationinString
 * @description Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
 * @param {String} s1 - The input string
 * @param {String} s2 - The input string
 * @return {boolean} - Returns true if s2 contains a permutation of s1, or false otherwise.
 */

function PermutationinString (s1, s2) {
  if (s1.length > s2.length) return false
  let start = 0
  let end = s1.length - 1
  const s1Set = SetHash()
  const s2Set = SetHash()
  for (let i = 0; i < s1.length; i++) {
    s1Set[s1[i]]++
    s2Set[s2[i]]++
  }
  if (equals(s1Set, s2Set)) return true
  while (end < s2.length - 1) {
    if (equals(s1Set, s2Set)) return true
    end++
    const c1 = s2[start]
    const c2 = s2[end]
    if (s2Set[c1] > 0) s2Set[c1]--
    s2Set[c2]++
    start++
    if (equals(s1Set, s2Set)) return true
  }
  return false
}
function equals (a, b) {
  return JSON.stringify(a) === JSON.stringify(b)
}

function SetHash () {
  const set = new Set()
  const alphabets = 'abcdefghijklmnopqrstuvwxyz'
  for (let i = 0; i < alphabets.length; i++) {
    set[alphabets[i]] = 0
  }
  return set
}

// Example 1:
// Input: s1 = "ab", s2 = "eidbaooo"
// Output: true
// Explanation: s2 contains one permutation of s1 ("ba").

// Example 2:
// Input: s1 = "ab", s2 = "eidboaoo"
// Output: false

最大和子数组

给定一个正整数数组和一个正数 k，找到长度为 k 的连续子数组的最大和。

def getMaxSum(arr, k): 
    maxSum = 0 
    windowSum = 0 
    start = 0 

    for i in range(len(arr)): 
        windowSum += arr[i] 

        if ((i - start + 1) == k): 
            maxSum = max(maxSum, windowSum) 
            windowSum -= arr[start] 
            start += 1 

    return maxSum

参考

• Window Sliding Technique - GeeksforGeeks (opens new window)
• 一文详解滑动窗口技术 - 知乎 (opens new window)