引用labuladong的一个关于滑动窗口的口诀 「滑动窗口老猛男，子串问题全靠它。左右指针滑窗口，一前一后齐头进。」

先看一段代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public static int maxStrSlidingWindow(String str) {
        // 定义一个滑动窗口
        // 1. 开始窗口中只有一个字母
        // 2. 窗口开始滑动加入第二个字母,如果distinct后count和窗口中元素相同,则说明没有重复
        // 3. 继续窗口中增加元素,如果如果distinct后count小于窗口中元素了,说明开始有重复了
        // 4. 删除窗口最前端(左端)元素,继续添加,窗口中保留的元素就是最长无重复子串
        LinkedList<Character> l = new LinkedList<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            l.add(c);
            long count = l.stream()
                    .distinct()
                    .count();
            if (l.size() != count) {
                l.removeFirst();
            }
        }
        return l.size();
    }

这段代码是干什么的呢？

这段代码其实就是一个leecode的「给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度」题，使用滑动窗口来解答的代码实现

也就是labuladong口诀中子串问题全靠它的具体体现。

左右指针滑窗口，一前一后齐头进 怎么理解

也就是代码中注释写的

  1. 定义了一个窗口`LinkedList
  2. 往这个List右侧add元素（也就是右指针滑动），一直添加元素到满足题目中（不含有重复字符）的临界点（也就是添加到元素已经在链表中出现过）
  3. 这时候需要收缩左侧指针l.removeFirst();，注意这时候每次实际只移除了一个元素
  4. 一前一后齐头进就是add一个，如果列表中有重复数据就会移除一个，也就是后进一步前跟进一步（右侧add，左侧remove），此时List内部对象是存在重复对象，但List整体长度是曾经出现过的 不含有重复字符的 最长子串 的长度的大小

一个实际的例子

1
2
3
4

public static void main(String[] args) {
    String str = "abcdefgaaaabcbbcmn";
    System.out.println(maxStrSlidingWindow(str));
}

遍历过程中List包含的元素情况如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

["a"]1
["a","b"]2
["a","b","c"]3
["a","b","c","d"]4
["a","b","c","d","e"]5
["a","b","c","d","e","f"]6
["a","b","c","d","e","f","g"]7
["a","b","c","d","e","f","g","a"]7
["b","c","d","e","f","g","a","a"]7
["c","d","e","f","g","a","a","a"]6
["d","e","f","g","a","a","a","a"]5
["e","f","g","a","a","a","a","b"]5
["f","g","a","a","a","a","b","c"]5
["g","a","a","a","a","b","c","b"]4
["a","a","a","a","b","c","b","b"]3
["a","a","a","b","c","b","b","c"]3
["a","a","b","c","b","b","c","m"]4
["a","b","c","b","b","c","m","n"]5
finally["b","c","b","b","c","m","n"]7