万字长文！滑动窗口看这篇就够了！

01

PART

从TCP滑动窗口讲起

滑动窗口协议（Sliding Window Protocol），属于TCP协议的一种应用，用于网络数据传输时的流量控制，以避免拥塞的发生。该协议允许发送方在停止并等待确认前发送多个数据分组。由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输，提高网络吞吐量。

大多数人接触滑动窗口应该是在TCP协议中，当我们从一个机器向另一个机器传输数据时，并不能一下子就传给对方。而是操作系统将这些数据变成连续的数据包，然后一部分一部分的传给对方。因为网络就好像一个沙漏，中间的连接管会决定网络传输的真实速度！

如果数据一口气发送给对方，说小点就是网络压力过大丢包重试，说大点没准就直接导致网络崩溃。那这里和滑动窗口有什么关系呢？当这些数据包一批一批的发送给对方的时候，其内部实质就是通过一个滑动窗口来维护数据。

下面两张图画的挺好，我就不造轮子了：

那为什么TCP这里要用滑动窗口来实现数据传输呢？因为我不是专门讲TCP的滑动窗口，所以我就简单说下：滑动窗口的大小可以依据策略动态调整，应用可根据自身的处理能力来控制窗口的大小，实现流量限制等功能。

（大概就是这么个玩意）

上面的知识，听懂了也好，没听懂也罢。至少到这里你需要知道两件事：

• 滑动窗口这玩意，并不是说面试的时候考考，真实场景也会用到！很重要！
• 滑动窗口的核心，说白了就丫一成语，张弛有度。（动态调整，容易扩展，可长可短，巴拉巴拉.....）

那我们算法里的滑动窗口，其实也是一码事。常用来处理一些连续问题。不管是固定窗口大小的，还是非固定窗口大小的（可变窗口），统统都属于滑动窗口类型的题目！下面我将通过几道经典例题，为大家讲解。

02

PART

滑动窗口最大值

先上一道难度比较高的题目！

第239题：给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值所构成的数组。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

解释:

滑动窗口的位置 最大值

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

本题对于题目没有太多需要额外说明的，应该都能理解，直接进行分析。我们很容易想到，可以通过遍历所有的滑动窗口，找到每一个窗口的最大值，来进行暴力求解。那一共有多少个滑动窗口呢，小学题目，可以得到共有 L-k+1 个窗口。

假设 nums = [1,3,-1,-3,5,3,6,7]，和 k = 3，窗口数为 6

根据分析，直接完成代码：

 1//java
 2class Solution {
 3    public int[] maxSlidingWindow(int[] nums, int k) {
 4        int len = nums.length;
 5        if (len * k == 0) return new int[0];
 6        int [] win = new int[len - k + 1];
 7        //遍历所有的滑动窗口
 8        for (int i = 0; i < len - k + 1; i++) {
 9            int max = Integer.MIN_VALUE;
10            //找到每一个滑动窗口的最大值
11            for(int j = i; j < i + k; j++) {
12                max = Math.max(max, nums[j]);
13            }
14            win[i] = max;
15        }
16        return win;
17    }
18}

It's Bullshit！结果令我们很不满意，时间复杂度达到了O(LK)，如果面试问到这道题，基本上只写出这样的代码，一定就挂掉了。那我们怎么样优化时间复杂度呢？有没有可以O(L)的实现呢？=_=

这里不卖关子，其实这道题比较经典，我们可以采用队列，DP，堆等方式进行求解，所有思路的主要源头应该都是在窗口滑动的过程中，如何更快的完成查找最大值的过程。但是最典型的解法还是使用双端队列。具体怎么来求解，一起看一下。

首先，我们了解一下，什么是双端队列：是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出或者插入。

我们可以利用双端队列来实现一个窗口，目的是让该窗口可以做到张弛有度（汉语博大精深，也就是长度动态变化。其实用游标或者其他解法的目的都是一样的，就是去维护一个可变长的窗口）

然后我们再做一件事，只要遍历该数组，同时在双端队列的头去维护当前窗口的最大值（在遍历过程中，发现当前元素比队列中的元素大，就将原来队列中的元素祭天），在整个遍历的过程中我们再记录下每一个窗口的最大值到结果数组中。最终结果数组就是我们想要的，整体图解如下。

假设 nums = [1,3,-1,-3,5,3,6,7]，和 k = 3

（个人认为我画的这个图是目前全网对于双端队列本题解法比较清晰的一个...所以我觉得如果不点个赞的话...晤..）

根据分析，得出代码：

 1//go
 2func maxSlidingWindow(nums []int, k int) []int {
 3    if len(nums) == 0 {
 4        return []int{}
 5    }
 6    //用切片模拟一个双端队列
 7    queue := []int{}
 8    result := []int{}
 9    for i := range nums {
10        for i > 0 && (len(queue) > 0) && nums[i] > queue[len(queue)-1] {
11            //将比当前元素小的元素祭天
12            queue = queue[:len(queue)-1]
13        }
14        //将当前元素放入queue中
15        queue = append(queue, nums[i])
16        if i >= k && nums[i-k] == queue[0] {
17            //维护队列，保证其头元素为当前窗口最大值
18            queue = queue[1:]
19        }
20        if i >= k-1 {
21            //放入结果数组
22            result = append(result, queue[0])
23        }
24    }
25    return result
26}

Perfact，题目完成！看着一下子超越百分之99的用户，是不是感觉很爽呢？

03

PART

滑动窗口的模式

滑动窗口的题目其实是一定模式的。对于大部分滑动窗口类型的题目，一般是考察字符串的匹配。比较标准的题目，会给出一个模式串B，以及一个目标串A。然后提出问题，找到A中符合对B一些限定规则的子串或者对A一些限定规则的结果，最终再将搜索出的子串完成题意中要求的组合或者其他。

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

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

再如：给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

都是属于这一类的标准题型。而对于这一类题目，我们常用的解题思路，是去维护一个可变长度的滑动窗口。无论是使用双指针，还是使用双端队列，又或者用游标等其他奇技淫巧，目的都是一样的。

04

PART

无重复字符的最长子串

在上文中，我们使用双端队列完成了滑动窗口的一道颇为困难的题目，以此展示了什么是滑动窗口。在本节中我们将继续深入分析，探索滑动窗口题型一些具有模式性的解法。

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

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

直接分析题目，假设我们的输入为“abcabcbb”，我们只需要维护一个窗口在输入字符串中进行移动。如下图：

当下一个元素在窗口没有出现过时，我们扩大窗口。

当下一个元素在窗口中出现过时，我们缩小窗口，将出现过的元素以及其左边的元素统统移出：

在整个过程中，我们记录下窗口出现过的最大值即可。而我们唯一要做的，只需要尽可能扩大窗口。

那我们代码中通过什么来维护这样的一个窗口呢？anyway~ 不管是队列，双指针，甚至通过map来做，都可以。

我们演示一个双指针的做法：

 1//java
 2public class Solution {
 3    public static int lengthOfLongestSubstring(String s) {
 4        int n = s.length();
 5        Set<Character> set = new HashSet<>();
 6        int result = 0, left = 0, right = 0;
 7        while (left < n && right < n) {
 8            //charAt：返回指定位置处的字符
 9            if (!set.contains(s.charAt(right))) {
10                set.add(s.charAt(right));
11                right++;
12                result = Math.max(result, right - left);
13            } else {
14                set.remove(s.charAt(left));
15                left++;
16            }
17        }
18        return result;
19    }
20}

通过观察，我们能看出来。如果是最坏情况的话，我们每一个字符都可能会访问两次，left一次，right一次，时间复杂度达到了O(2N)，这是不可饶恕的。不理解的话看下图：

假设我们的字符串为“abcdc”，对于abc我们都访问了2次。

那如何来进一步优化呢？

其实我们可以定义字符到索引的映射，而不是简单通过一个集合来判断字符是否存在。这样的话，当我们找到重复的字符时，我们可以立即跳过该窗口，而不需要对之前的元素进行再次访问。

 1//java
 2public class Solution {
 3    public static int lengthOfLongestSubstring(String s) {
 4        int n = s.length(), result = 0;
 5        Map<Character, Integer> map = new HashMap<>(); 
 6        for (int right = 0, left = 0; right < n; right++) {
 7            if (map.containsKey(s.charAt(right))) {
 8                left = Math.max(map.get(s.charAt(right)), left);
 9            }
10            result = Math.max(result, right - left + 1);
11            map.put(s.charAt(right), right + 1);
12        }
13        return result;
14    }
15}

修改之后，我们发现虽然时间复杂度有了一定提高，但是还是比较慢！如何更进一步的优化呢？我们可以使用一个256位的数组来替代hashmap，以进行优化。（因为ASCII码表里的字符总共有128个。ASCII码的长度是一个字节，8位，理论上可以表示256个字符，但是许多时候只谈128个。具体原因可以下去自行学习~）

 1//java
 2class Solution {
 3    public int lengthOfLongestSubstring(String s) {
 4        int len = s.length();
 5        int result = 0;
 6        int[] charIndex = new int[256];
 7        for (int left = 0, right = 0; right < len; right++) {
 8            char c = s.charAt(right);
 9            left = Math.max(charIndex[c], left);
10            result = Math.max(result, right - left + 1);
11            charIndex[c] = right + 1;
12        }
13        return result;
14    }
15}

我们发现优化后时间复杂度有了极大的改善！这里简单说一下原因，对于数组和hashmap访问时，两个谁快谁慢不是一定的，需要思考hashmap的底层实现，以及数据量大小。但是在这里，因为已知了待访问数据的下标，可以直接寻址，所以极大的缩短了查询时间。

05

PART

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

如果完成上面两道题的学习，相信大家对滑动窗口已不陌生。下面继续完成一道题目，来进行巩固学习。

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

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

说明：

字母异位词指字母相同，但排列不同的字符串。

不考虑答案输出的顺序。

示例 1:

输入:

s: "cbaebabacd" p: "abc"

输出:

[0, 6]

解释:

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

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

示例 2:

输入:

s: "abab" p: "ab"

输出:

[0, 1, 2]

解释:

起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。

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

起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

直接套用之前的模式，使用双指针来模拟一个滑动窗口进行解题。分析过程如下：

假设我们有字符串为“cbaebabacd”，目标串为“abc”

我们通过双指针维护一个窗口，由于我们只需要判断字母异位词，我们可以将窗口初始化大小和目标串保持一致。（当然，你也可以初始化窗口为1，逐步扩大）

而判断字母异位词，我们需要保证窗口中的字母出现次数与目标串中的字母出现次数一致。这里因为字母只有26个，直接使用数组来替代map进行存储（和上一讲中的ASCII使用256数组存储思想一致）。

pArr为目标串数组，sArr为窗口数组。我们发现初始化数组，本身就满足，记录下来。（这里图示用map模拟数组，便于理解）

然后我们通过移动窗口，来更新窗口数组，进而和目标数组匹配，匹配成功进行记录。每一次窗口移动，左指针前移，原来左指针位置处的数值减1，表示字母移出；同时右指针前移，右指针位置处的数值加1，表示字母移入。详细过程如下：

最终，当右指针到达边界，意味着匹配完成。然后我们根据分析，给出代码（整个题解都是套用之前的解题套路。）

class Solution {

    public List<Integer> findAnagrams(String s, String p) {

        if (s == null || p == null || s.length() < p.length()) return new ArrayList<>();

        List<Integer> list = new ArrayList<>();

        int[] pArr = new int[26];
        int[] sArr = new int[26];

        for (int i = 0; i < p.length(); i++) {
            sArr[s.charAt(i) - 'a']++;  
            pArr[p.charAt(i) - 'a']++;
        }

        for (int i = 0; i < p.length(); i++) {
            int index = p.charAt(i) - 'a';
        }

        int i = 0;
        int j = p.length();

        // 窗口大小固定为p的长度
        while (j < s.length()) {
            if (isSame(pArr, sArr))
                list.add(i);            
            //sArr[s.charAt(i) - 'a']-- 左指针位置处字母减1
            sArr[s.charAt(i) - 'a']--;
            i++;
            //sArr[s.charAt(j) - 'a']++ 右指针位置处字母加1
            sArr[s.charAt(j) - 'a']++;
            j++;
        }

        if (isSame( pArr, sArr))
            list.add(i);

        return list;
    }

    public boolean isSame(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; ++i)
            if (arr1[i] != arr2[i])
                return false;
        return true;
    }
}

当然，这种解法并不是最优解！大家有兴趣的话，可以下去自行再研究一下如何在该解法的基础上再进行优化。