滑动窗口算法是较为入门题目的算法，一般是一些有规律数组问题的最优解，也就是说，如果一个数组问题可以用动态规划解，但又可以使用滑动窗口解决，那么往往滑动窗口的效率更高。

 

双指针也并不局限在数组问题，像链表场景的 “快慢指针” 也属于双指针的场景，其快慢指针滑动过程中本身就会产生一个窗口，比如当窗口收缩到某种程度，可以得到一些结论。

 

因此掌握滑动窗口非常基础且重要，接下来按照我的经验给大家介绍这个算法。

 

精读

 

滑动窗口使用双指针解决问题，所以一般也叫双指针算法，因为两个指针间形成一个窗口。

 

什么情况适合用双指针呢？一般双指针是暴力算法的优化版，所以：

 

如果题目较为简单，且是数组或链表问题，往往可以尝试双指针是否可解。

 

如果数组存在规律，可以尝试双指针。

 

如果链表问题限制较多，比如要求 O(1) 空间复杂度解决，也许只有双指针可解。

 

也就是说，当一个问题比较有规律，或者较为简单，或较为巧妙时，可以尝试双指针（滑动窗口）解法。

 

我们还是拿例子说明，首先是两数之和。

 

两数之和

 

两数之和是一道简单题，实际上和滑动窗口没什么关系，但为了引出三数之和，还是先讲这道题。题目如下：

 

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

 

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

 

暴力解法就是穷举所有两数之和，发现和为 target 结束，显然这种做法有点慢，我们换一种思路。

 

由于可以用空间换时间，又只有两个数，我们可以对题目进行转化，即通过一次遍历，将 nums 每一项都减去 target，然后找到后面任意一项值为前面的结果，即表示它们和为 target。

 

可以用哈希表 map 加速查询，即将每一项 target - num 作为 key，如果后面任何一个 num 作为 key 可以在 map 中找到，则得解，且上一个数的原始值可以存在 map 的 value 中。这要仅需遍历一次，时间复杂度为 O(n)。

 

之所以说这道题，是因为这道题是单指针，即只有一个指针在数组中移动，并配合哈希表快速求解。对于稍微复杂的问题，单指针就不够了，需要用双指针解决（一般来说不会用到三或以上指针），那复杂点的题目就是三数之和了。

 

三数之和

 

三数之和是一道中等题，别以为只是两数之和的加强版，其思路完全不同。题目如下：

 

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

 

由于超过了两个数，所以不能像双指针一样求解了，因为即便用了哈希表存储，也会在遍历时遇到 “两数之和” 的问题，而哈希表方案无法继续嵌套使用，即无法进一步降低复杂度。

 

为了降低时间复杂度，我们希望只遍历一次数组，这就需要数组满足一定条件我们才能用滑动窗口，所以我们对数组进行排序，使用快排的时间复杂度为 O(nlogn)，时间复杂度已超出两数之和，不过因为题目复杂，这个牺牲是无法避免的。

 

假设从小到大排序，那我们就拿到一个递增数组了，此时经典滑动窗口方法就可用了！怎么滑动呢？首先创建两个指针，分别叫 left 与 right，通过不断修改 left 与 right，让它们在数组间滑动，这个窗口大小就是符合题目要求的，当滑动完毕时，返回所有满足条件的窗口即可，记录其实很简单，只要在滑动过程中记录一下就行。

 

首先排除异常值，即数组长度过小，然后对于常规情况，我们拿一个全局变量存储当前窗口数的和，这样 right + 1 只要累加 nums[right+1]，left + 1 只要减去 nums[left] 即可快速拿到求和。

 

由于需要考虑所有情况，所以需要一次数组遍历，对于每次遍历的起始点 i，如果 nums[i] > 0 则直接跳过，因为数组排序后是递增的，后面的和只会永远大于 0；否则进行窗口滑动，先形成三个点 [i, i+1, n-1]，这样保持 i 不动，不断包夹后两个数字即可，只要它们的和大于 0，就将第三个点左移（数字会变小），否则将第二个点右移（数字会变大），其实第二个和第三个数就是滑动窗口。

 

这样的话时间复杂度是 O(n²)，因为存在两次遍历，忽略快排较小的时间复杂度。

 

那么四数之和，五数之和呢？

 

四数之和

 

该题和三数之和完全一样，除了要求变成四个数。

 

首先还是排序，然后双重递归，即确定前两个数不变，不断包夹后两个数，后两个数就是 i+1 和 n-1，算法和三数之和一样，所以最终时间复杂度为 O(n³)。

 

那么 N 数之和（N > 2）都可以采用这个思路解决。

 

为什么没有更优的方法呢？我想可能因为：

 

无论几数之和，快排一次时间复杂度都是固定的，所以沿用三数之和的方案其实占了排序算法便宜。

 

滑动窗口只能用两个指针进行移动，而没有三指针但又保持时间复杂度不变的窗口滑动算法存在。

 

所以对于 N 数之和，通过排序付出了 O(nlogn) 时间复杂度之后，可以用滑动窗口，将 2 个数时间复杂度优化为 O(n)，所以整体时间复杂度就是 O(N - 2 + 1 个 n)，即 O(N-1 个 n)，而最小的时间复杂度 O(n²) 比 O(nlogn) 大，所以总是忽略快排的时间复杂度，所以三数之和时间复杂度是 O(n²)，四数之和时间复杂度为 O(n³)，依此类推。

 

可以看到，我们从最简单的两数之和，到三数之和、四数之和，跨入了滑动窗口的门槛，本质上是利用排序后数组有序的特性，让我们在不用遍历数组的前提下，可以对窗口进行滑动，这是滑动窗口算法的核心思想。

 

为了加强这个理解，再看一道类似的题目，无重复字符的最长子串。

 

无重复字符的最长子串

 

无重复字符的最长子串是一道中等题，题目如下：

 

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

 

由于最长子串是连续的，所以显然可以考虑滑动窗口解法。其实确定了滑动窗口解法后，问题很简单，只要设定 left 和 right，并用一个哈希 Set 记录哪些元素存在过，在过程中记录最大长度，并尝试 right 右移，如果右移过程中发现出现重复字符，则 left 右移，直到消除这个重复字符为止。

 

解法并不难，但问题是，我们要想清楚，为什么用滑动窗口遍历一次就可以做到 不重不漏？即这道题时间复杂度只有 O(n) 呢？

 

只要想明白两个问题：

 

由于子串是连续的，既然不存在跳跃的情况，只要一次滑动窗口内能包含所有解，就涵盖了所有情况。

 

一次滑动窗口内不包含什么？由于我们只将 right 右移，且出现重复后尝试将 left 右移到不重复后，right 再继续右移，这忽略了出现重复后， right 左移的情况。

 

我们重点看二个问题，显然，如果 abcd 这四个连续的字符不重复，那么 left 右移后，bcd 也显然不重复，所以如果此时就可以将 right 右移形成 bcda 的窗口继续找下去，而不需要尝试 bc 这种情况，因为这种情况虽然不重复，但一定不是最优解。

 

好了，通过这个例子我们看到，滑动窗口如何缩小窗口范围其实不难，但更要注重的是，背后对于为什么可以用滑动窗口的思考，滑动窗口有没有做到不重不漏，如果没有想清楚，可能整个思路都错了。

 

那么滑动窗口的应用已经说透了？其实没有，我们上面只说了缩小窗口这种比较单一的脑回路，其实双指针构成的滑动窗口不一定都是那么正常滑的，一种有意思的场景是快慢指针，即是以相对速度决定窗口如何滑动。

 

关于快慢指针，经典的题目有环形链表、删除有序数组中的重复项。