滑动窗口策略

本文阐述了基于 滑动窗口 策略的解决问题的思考路径，对应 leetcode 以下题目：

滑动窗口基础

通俗点来说，滑动窗口策略是基于快慢 双指针 策略和 顺序 存储结构（如 golang 中 array，slice，string）实现的一种解决问题的方法。该策略广泛应用于子串查找，处理等方面。如在 TCP 和 OSI 模型中的 Data link layer 都使用了 sliding window protocol 来提高高延迟下的传输效率。

基于以上对 滑动窗口 策略的定义，通过滑动窗口解决问题不外乎在解决：

什么时候扩大窗口；
什么时候缩小窗口；

那么个根据以上思考逻辑可以得到以下 滑动窗口 框架的伪代码：

func slidingWindow(str string) {
  slow, fast := 0, 0

  for fast < len(str) {
    // 扩大窗口
    current := str[fast]
    fast++

    // 缩小窗口
    for shouldWeShrinkWindow() {
      slow++
      // 老的 slow 因 slow 指针递增而移除窗口，此处应对移除窗口项进行额外处理
    }
  }
}

由上伪代码可知，滑动窗口核心很纯粹简洁，而 其难点在于判断扩大窗口的时机和缩小窗口的时机。

无重复字符的最长子串

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

该问题本质在于通过滑动窗口找到所有不含重复字符的子串，并在其中找到最长子串。那么不含重复字符表示当前字符迭代中，若字符频率大于 1 时，应缩小窗口，直到字符频率为 1。

思考路径

每次扩大窗口时，都记录递增新的字符频率：
go
```
current := s[fast]
fast++
windowMap[current]++
```
当存在当前字符的频率大于 1 时，那么即存在重复字符，那么尝试缩小字符，即在此场景中缩小窗口的条件为 windowMap[current] > 1，进而得到窗口中的无重复最小子串：
go
```
for windowMap[current] > 1 {
  deleted := s[slow]
  slow++
  windowMap[slow]--
}
```

实现

代码如下：

func lengthOfLongestSubstring(s string) int {
  fast, slow, windowMap := 0, 0, map[byte]int{}
  answer, validInWindow = 0, []int{}

  for fast < len(s) {
    current := s[fast]
    fast++
    windowMap[current]++

    for windowMap[current] > 1 {
      deleted = s[slow]
      slow++
      windowMap[slow]--
    }

    answer = max(right - left, answer)
  }

  return answer
}

func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}

因为快慢指针遍历了整个字符串一次，那么此算法时间复杂度为 O(N)，另外通过构建了一个字符频率的映射，那么空间复杂度为 O(|Σ|)，其中 |Σ| 表示字符集的大小。

异位词基础

后文题目会涉及异位词的概念，首先解释一下异位词。异位词解释为存在一个单词，和另一个比较单词，组成二者的所有字符的频率相等，但字符的排列不同。

对应以下 leetcode 问题：

242 有效的字母异位词

这里涉及字符的频率统计，那么不难想到通过哈希映射结构存储频率信息，最大键个数为 26，即 26 个字母。之后如何确定频率相等的问题呼之欲出。这里我们常规可以通过其中一个目标字串的哈希映射逐个比较它们的字符频率是否相等，另外一种方式是在构建一个字符串的频率映射时，减去在另外一个字符串中的 相同位置 的字符频率，那么如果二者为异位词时，最终我们将得到一个所有键值为 0 的哈希映射。伪代码如下：

func isAnagram(s, t string) bool {
  if isNotEqualLength(s, t) {
    return false
  }

  charMap := map[byte]int{}

  for i := 0; i < len(s); i++ {
    addFreq(s[i])
    removeFreq(s[i])
  }

  for key := range charMap {
    if isNotZero(charMap[key]) {
      return false
    }
  }

  return true
}

最终实现代码如下：

func isAnagram(s string, t string) bool {
  if len(s) != len(t) {
    return false
  }

  charMap := map[byte]int{}

  for i := 0; i < len(s); i++ {
    charMap[s[i]]++
    charMap[t[i]]--
  }

  for key := range charMap {
    if charMap[key] != 0 {
      return false
    }
  }

  return true
}

因为遍历了字符串一次，那么时间复杂度为 O(N)。另外，我们额外使用了存储空间，但该空间占用始终固定为 26 大小（26 个字母），那么空间复杂度为 O(1)。

找到字符串中所有字母异位词

原题对应如下：

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。不考虑答案输出的顺序。

该题的核心问题是在 s 中找到 p 的异位词子串，那么换句话说，p 是 s 的子串的排列。而对于异位词的处理，前文已经阐述通过构建哈希映射，并通过双指针下的频率计算找到目标异位词。结合滑动窗口策略，窗口字符串长度始于 0，在窗口字符串小于目标字符串长度时，且存在目标字符串中的字符时，进行扩大窗口；当不小于目标字符串长度时，表示当前窗口可能存在目标字符串的异位词，那么开始逐步缩小窗口。

伪代码如下：

func findAnagrams(s, p string) []int {
  slow, fast, needsMap, windowMap := 0, 0, map[byte]int, map[byte]int
  answer, validInWindow := []int{}

  createNeedsMap(needsMap, p)

  for isInString(fast) {
    current := windowMap[fast]
    expandWindow()
    if isInNeedsMap(current) {
      windowMap[current]++
      if isSameFreq(needsMap[current], windowMap[current]) {
        validInWindow++
      }
    }

    // 只要窗口长度不小于 p，那么就尝试缩小窗口
    for isEqual(fast - slow, len(needsMap)) {
      if isAnagram(validInWindow) {
        answer = append(answer, slow)
      }
      shrinkWindow()
      recoverLeftPointerFreq()
    }
  }

  return answer
}

构建字符映射

在上文伪代码中，首先通过以下代码构建字符频率映射：

if isInNeedsMap(current) {
  windowMap[current]++
  // ...
}

当且仅当当前的字符是出现过 p 中的，那么就在 windowMap 中记录，而 windowMap 即为 窗口内 所有在 p 中存在过的字符的频率映射，注意，这里最终 windowMap 中单个字符的频率不一定等于 needsMap 中的频率，大于，小于，等于都有可能。

再通过以下逻辑实现统计 windowMap 中存在的频率 大于或等于 needsMap 中的频率的字符个数，此举最终是为了我们在缩小窗口时，提供判断异位词依据。

if needsMap[current] == windowMap[current] {
  validInWindow++
}

在 windowMap[current] 等于对应字符在 needsMap 中的频率时，validInWindow 递增。那么在准备缩小窗口时，存在 validInWindow 个频率大于等于 needsMap 中对应字符的频率的字符，那么此窗口中可能包含了有效的异位词。

缩小窗口

前文已经阐述，基于滑动窗口策略解决问题时，关键点之一就是判断何时缩小窗口。基于本题异位词的判断，我们在 fast 和 slow 指针所构成的窗口大于 p 字符串的长度时，缩小窗口。因为当窗口大小不小于目标字符串 p 时，那么就有可能存在 p 的异位词。

for (fast - slow) == len(p) {
  // 进行异位词检测
}

当我们缩小窗口时，发现当前的 validInWindow 等于 needsMap 的大小（前文已经说明 validInWindow 仅在 needsMap[current] == windowMap[current] 才会递增），那么我们可以直接判断此时存在异位词，且始于窗口的开始位置 —— slow 慢指针。

for (fast - slow) == len(p) {
  // 异位词检测
  if validInWindow == len(needsMap) {
    answer = append(answer, slow)
  }
  // ...
}

当异位词判断完成后，不论成功与否，继续执行之后的窗口操作。这里值得注意的是，在缩小窗口时，应该把移除窗口的项的频率恢复，该操作本质上是之前构建频率映射的逆向操作，即：

for (fast - slow) == len(p) {
  // ... 异位词检测
  deleted := s[slow]
  slow++
  if _, ok := needsMap[deleted]; ok {
    if needsMap[deleted] == windowMap[deleted] {
      validInWindow--
    }
    windowMap[deleted]--
  }
}

至此，完成一个完整的缩小窗口操作。

实现

最终实现代码如下：

func findAnagram(s, p string) []int {
  slow, fast, needsMap, windowMap := 0, 0, map[byte]int, map[byte]int
  answer, validInWindow := []int{}, 0

  for i := 0; i < len(p); i++ {
    needsMap[p[i]]++
  }

  for fast < len(s) {
    current := s[fast]
    fast++
    if _, ok := needsMap[current]; ok {
      windowMap[current]++
      if needsMap[current] == windowMap[current] {
        validInWindow++
      }
    }

    for (fast-slow) == len(p) {
      if validInWindow == len(needsMap) {
        answer = append(answer, slow)
      }
      deleted := s[slow]
      slow++
      if _, ok := needsMap; ok {
        if needsMap[deleted] == windowMap[deleted] {
          validInWindow--
        }
        windowMap[deleted]--
      }
    }
  }

  return answer
}

算法中快慢指针遍历了字符串一次，那么时间复杂度为 O(N)，额外的字符映射恒为 26 个字符大小，即空间使用与输入无关，那么空间复杂度为 O(1)。

字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

本题与找到字符串中所有字母异位词思考路径相似，不同之处在于找到符合题意得子串后直接返回 true。那么借鉴前文思路有以下实现代码：

func checkInclusion(s1, s2 string) bool {
  slow, fast, needsMap, windowMap := 0, 0, map[byte]int{}, map[byte]int{}
  validInWindow := 0

  for i := 0; i < len(s1); i++ {
    needsMap[s1[i]]++
  }

  for fast < len(s2) {
    current := s2[fast]
    fast++
    if _, ok := needsMap[current]; ok {
      windowMap[current]++
      if needsMap[current] == windowMap[current] {
        validInWindow++
      }
    }

    for (fast - slow) == len(s1) {
      if validInWindow == len(needsMap) {
        return true
      }
      deleted := s2[slow]
      slow++
      if _, ok := needsMap[deleted]; ok {
        if needsMap[deleted] == windowMap[deleted] {
          validInWindow--
        }
        windowMap[deleted]--
      }
    }
  }

  return false
}

最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。示例：

输入: S = "ADOBECODEBANC", T = "ABC"

输出: "BANC"

本题缩小窗口的时机与之前异位词相关的滑动窗口的缩小条件不同的是，当窗口中的包含了所有目标字符串中的字符时，就是符合题意得子串之一。那么得到 缩小窗口的条件 应该是：

当且仅当窗口内的字符频率大于大于等于目标字符串时，此时才会存在子串，而不是窗口大小不小于目标字符串的长度。伪代码如下：

func minWindow(s, t string) string {
  createNeedsMap(t)

  for fast < len(s) {
    expandWindow()
    recordExpandItemState()

    for validInWindow < len(needsMap) {
      if isWindowSmallerThanAnswer() {
        setNewAnswer()
      }
      shrinkWindow()
      recoverShrinkingItemState()
    }
  }

  return answer
}

实现

最终实现代码如下：

func minWindow(s,t string) string {
  slow, fast, needsMap, windowMap := 0, 0, map[byte]int{}, map[byte]int{}
  validInWindow, start, length := 0, 0, math.MaxInt32

  for i := range t {
    needsMap[t[i]]++
  }

  for fast < len(s) {
    current := s[fast]
    fast++
    if _, ok := needsMap[current]; ok {
      windowMap[current]++
      if needsMap[current] == windowMap[current] {
        validInWindow++
      }
    }

    for validInWindow == len(needsMap) {
      if (fast - slow)  < length {
        start = slow
        length = fast - slow
      }
      deleted := s[slow]
      slow++
      if _, ok := needsMap[deleted]; ok {
        if needsMap[deleted] == windowMap[deleted] {
          validInWindow--
        }
        windowMap[deleted]--
      }
    }
  }

  if length == math.MaxInt32 {
    return ``
  }
  return s[start:(start+length)]
}

思路抽象

至此，对于本文出现得一类基于字符串的子串，异位词等场景，我们可以通过 滑动窗口 实现高效的字符串比较。而对于字符串查找这一类 滑动窗口 可以总结出以下思考路径：

将目标字符串 t 转换为字符与频率的映射 needsMap；
go
```
for i := range t {
  needsMap[t[i]]++
}
```
创建快慢指针，始于待测字符串 s 的 0 索引字符；
go
```
slow, fast := 0, 0
```

创建内外嵌套迭代结构来实现增大窗口和缩小窗口，每次迭代时，都通过移动 fast 指针实现扩大窗口，通过移动 slow 指针实现缩小窗口；

for fast < len(s) {
  current := s[fast]
  fast++
  // ...
  for shouldShrinkWindow() {
     // ...
     deleted := s[slow]
     slow++
  }
}

在增大窗口时，仅记录与 needsMap 重叠的字符，当与 needsMap 中同名字符存在相同频率时，额外递增 validInWindow 计数器。

if _, ok := needsMap[current]; ok {
  windowMap[current]++
  if needsMap[current] == windowMap[current] {
    validInWindow++
  }
}

在达到缩小窗口的条件时，首先判断是否能加入结果数组，之后移动 slow 指针实现缩小窗口。额外地，对于移除窗口的字符，若该字符频率与 needsMap 同名字符频率相等时，递减 validInWindow 计数器，之后递减 windowMap 中的对应字符频率。本质上 缩小窗口的恢复字符统计操作是增大窗口时递增字符统计操作的 逆向操作。
go
```
// handler result from here ...

// recover state
if _, ok := needsMap[deleted]; ok {
  if needsMap[deleted] == windowMap[deleted] {
    validInWindow--
  }
  windowMap[deleted]--
}
```

示范

根据以上思路，可以得到以下示范代码：

func slidingWindow(s, t string){
  slow, fast, needsMap， windowMap := map[byte]int{}, map[byte]int{}

  for i := range t {
    needsMap[t[i]]++
  }

  for fast < len(s) {
    current := s[fast]
    fast++
    if _, ok := needsMap[current]; ok {
      windowMap[current]++
      if needsMap[current] == windowMap[current] {
        validInWindow++
      }
    }

    for shrinkCondition() {
      tryToAppendAnswer()

      deleted := s[slow]
      slow++
      if _, ok := needsMap[deleted]; ok {
        if needsMap[deleted] == windowMap[deleted] {
          validInWindow--
        }
        windowMap[deleted]--
      }
    }
  }
}