滑动窗口(Sliding Window)算法框架
洪笳淏 Lv4
 2021-04-28 14:47:30      

  滑动窗口主要应用于子串问题，遇到这类问题不要犹豫，直接考虑使用滑动窗口。作为双指针类问题最难掌握的技巧，其设计思路其实非常简单，就是通过两个指针维护一个窗口，通过前后指针的不断向前滑动，然后更新答案。该算法的大致逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
left := 0
right := 0

for right < s.size() {
  // 增大窗口
  window.add(s[right])
  right++
  
  for window needs shrink {
    // 缩小窗口
    window.remove(s[left])
    left++
  }
}

  这个算法技巧的时间复杂度是 O(N)，比字符串暴力算法要高效得多。其实困扰大家的，不是算法的思路，而是各种细节问题。比如说如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。即便你明白了这些细节，也容易出 bug，找 bug 还不知道怎么找，真的挺让人心烦的。

算法框架

滑动窗口算法代码框架

  废话少说，直接上代码。下面的框架很适合给出了具体t，要求找出其在主串s中的排列或包含t的子串的问题，可以直接套用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func slidingwindow(s string, t string) { // s是主串，t是子串
  
  // 根据题目条件灵活选择数据结构，其主要作用和目的是判断左边界是否要右移
  need := make(map[byte]int, len(t))  // need用于记录t子串对字符的实际要求
  window := make(map[byte]int, len(t)) // window用于检测当前窗口内满足t子串的要求字符的实际情况
  
  for i:=0; i<len(t); i++ {
    need[t[i]] = 1  // 数量可以是任意数字，根据题目实际需求
  }
  
  var (
  	left = 0 // 窗口左边界
    right = 0 // 窗口右边界
    valid = 0 // 满足条件的字符个数
  )
  
  for right < len(s) {
    // c是要移入窗口的字符
    c := s[right]
    // 右移窗口
    right++
    // 进行窗口内数据的一系列更新
    ...
    
    /*** debug 输出的位置 ***/
    fmt.Printf("window: [%d, %d)\n", left, right);
    /********************/
    
    // 判断左侧窗口是否要收缩
    for window needs shrink {
      // d 是将移出窗口的字符
      d := s[left]
      // 左移窗口
      left++
      // 进行窗口内数据的一系列更新
      ...
    }
  }
}

示例

最小覆盖子串

avatar

就是说要在 S(source) 中找到包含 T(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的。

如果我们使用暴力解法，代码大概是这样的：

1
2
3
4
5
6
7
for i:=0; i<len(s); i++ {
  for j:=i+1; j<len(s); j++ {
    if s[i:j] 包含t中的所有字母 {
      更新答案
    }
  }
}

思路很直接，但是显然，这个算法的复杂度肯定大于 O(N^2) 了。

滑动窗口算法的思路是这样：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。

初始状态：

image-20210429193510364

增加 right，直到窗口 [left, right] 包含了 T 中所有字符：

image-20210429193608894

现在开始增加 left，缩小窗口 [left, right]。

image-20210429193630917

直到窗口中的字符串不再符合要求，left 不再继续移动。

image-20210429194033697

之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。

现在开始套模板，只需要思考以下四个问题：

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？

3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
func minWindow(s string, t string) string {
    need := map[byte]int{} // 根据t子串记录实际的需求
    window := map[byte]int{} // 记录窗口内满足要求的字符的情况
  
    for i:=0; i<len(t); i++ { // 将子串t中字符的实际需求用need来记录
        need[t[i]]++
    }
  
    var (
  	    left = 0
        right = 0
        valid = 0
      
        // 本题要求返回子串，所以引入start和length来记录子串的起始和长度
        start = 0 // 记录最小覆盖子串的起始索引
        length = len(s)+1 //记录最小覆盖子串的长度
    )
  
    for right < len(s) {
        // 加入窗口
        c := s[right]
        // 右移窗口
        right++
    
        // 检查c是否在need的需求中，若在则加入window(进行窗口内数据的一系列更新)
        if _, ok := need[c]; ok {
          window[c]++     
          // 若字符c的个数已经满足了need中的要求
    	    if window[c] == need[c] {
      	        valid++
    	    }
        }
        // fmt.Printf("window1: [%d, %d)\n", left, right)  // debug专用
        // 当window内的所有字符都满足了需求，判断左侧窗口是否要收缩
        for valid == len(need) {
            if right - left < length {
                start = left
                length = right - left
            }
      
            // d 是将移出窗口的字符
            d := s[left]
            // 左边界右移缩小窗口
            left++
            // 进行窗口内数据的一系列更新
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
            // fmt.Printf("window2: [%d, %d)\n", left, right)  // debug专用      
        }
    }
  
    if length == len(s)+1 {
        return ""
    } else {
        return s[start:start+length]
    }  
}

字符串的排列

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

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

示例 1：

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例 2：

输入: s1= “ab” s2 = “eidboaoo”
输出: False

提示：

  • 输入的字符串只包含小写字母
  • 两个字符串的长度都在 [1, 10,000] 之间

这种题目，是明显的滑动窗口算法，相当给你一个 S1 和一个 **S2**，请问你 S2 中是否存在一个子串，包含 S1 中所有字符且不包含其他字符？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func checkInclusion(s1 string, s2 string) bool {
    need := map[byte]int{}
    window := map[byte]int{}

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

    var (
        left = 0
        right = 0
        valid = 0
    )

    for right < len(s2) {
        window[s2[right]]++
				
      	// 进行窗口内数据的一系列更新
        if _, ok := need[s2[right]]; ok {
            if window[s2[right]] == need[s2[right]] {
                valid++
            }
        }
        right++
        
      	// 在这里判断是否找到了合法的子串
        if valid == len(need) {
            return true
        }

        if right >= len(s1) {
            if _, ok := need[s2[left]]; ok {
                if window[s2[left]] == need[s2[left]] {
                    valid--
                }
            }
            window[s2[left]]--
            left++
        }   
    }
    return false
}

对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：

1、本题移动 left 缩小窗口的时机是窗口大小大于 S1.size() 时，应为排列嘛，显然长度应该是一样的。

2、当发现 valid == len(need) 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。

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

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

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

说明：

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

示例 1:

1
2
3
4
5
6
7
8
9
输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

1
2
3
4
5
6
7
8
9
10
输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

和上一个示例几乎一模一样，只不过函数返回的东西不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func findAnagrams(s string, p string) []int {
    need := map[byte]int{}
    window := map[byte]int{}
    ret := []int{}

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

    var (
        left = 0
        right = 0
        valid = 0
    )

    for right < len(s) {
        c := s[right]
        window[c]++
        right++

        if _,ok := need[c]; ok{
            if window[c] == need[c] {
                valid++
            }
        }

        if valid == len(need) {
            ret = append(ret, left)
        }

        if right >= len(p) {
            d := s[left]
            if _,ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
            }
            window[d]--
            left++
        }
    }
    return ret
}

无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

1
2
输入: s = ""
输出: 0

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

  这个题终于有了点新意，不是一套框架就出答案，不过反而更简单了，稍微改一改框架就行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func lengthOfLongestSubstring(s string) int {
    window := map[byte]int{}

    left, right := 0, 0
    ret := 0

    for right < len(s) {
        c := s[right]
        window[c]++
        right++

      	// 每当新进入窗口的字符出现多次，窗口左边界便开始右移，知道窗口内没有重复字符
        for window[c]>1 { 
            d := s[left]
            window[d]--
            left++
        }
        ret = max(ret, right-left)
    }
    return ret
}

func max(a, b int) int {
    if a>b {
        return a
    }
    return b
}
  • Post title：滑动窗口(Sliding Window)算法框架
  • Post author：洪笳淏
  • Create time：2021-04-28 14:47:30
  • Post link：https://jiahaohong1997.github.io/2021/04/28/滑动窗口(Sliding-Window)算法框架/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments