Javatv

# 滑动窗口

# 滑动窗口

滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

一般对于滑动窗口的定义比较难懂，个人根据字面意思去定义，把他拆分为：

  • 滑动：窗口是不固定的，可以移动。
  • 窗口：窗口能大能小，所以窗口的大小也是不固定的，可大可小。

# 一个栗子

题目描述：无重复字符的最长子串 (opens new window)

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

示例：

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

对我一个刚开始来刷题的人来说，根本不知道什么是滑动窗口，用了最简单粗暴地方式来处理（多重循环），提交了7次，有4次错误，2次超时，最后去了解了滑动窗口才通过。

image-20210827155114981

# 解题思路

官方：找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案，其中括号中表示选中的字符以及最长的字符串：

  • 以 (a)bcabcbb 开始的最长字符串为(abc)abcbb；

  • 以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；

  • 以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；

  • 以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；

  • 以 abca(b)cbb 开始的最长字符串为 abca(bc)bb；

  • 以 abcab(c)bb 开始的最长字符串为 abcab(cb)b；

  • 以 abcabc(b)b 开始的最长字符串为 abcabc(b)b；

  • 以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。

图解

我们定义两个指针i,j来控制窗口的移动和大小

image-20210827165924612

# 代码实现

public static int lengthOfLongestSubstring3(String s) {
    int len = s.length();
    int max = 0, i = 0, j = 0;
    //定义一个窗口
    Set<Character> set = new HashSet<>();
    while (i < len && j < len) {
        //如果不存在则加入
        if (!set.contains(s.charAt(j))) {
            //增大窗口
            set.add(s.charAt(j));
            j++;//索引从0开始，所以+1之后在计算
            max = Math.max(max, j - i);
        } else {
            //存在就删除窗口
            set.remove(s.charAt(i));
            i++;
        }
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 时间复杂度

在最坏的情况下，while 循环中的语句会执行 2n 次，例如 abcdefgg，开始的时候 j 一直后移直到到达第二个 g 的时候固定不变 ，然后 i 开始一直后移直到 n ，所以总共执行了 2n 次，时间复杂度为 O(n)。

# 其他

← 动态规划 →