目录
滑动窗口算法
首先介绍一下什么是滑动窗口：滑动窗口算法是一种在数组或字符串中寻找特定模式的算法，它可以在 O(n) 的时间复杂度内解决一些字符串或数组相关的问题。
基本思想
滑动窗口算法的基本思想是维护一个窗口，窗口内是需要处理的数据，每次移动窗口时，我们只需要计算新窗口与旧窗口的区别即可，这样可以大大减少计算量。
具体地说，滑动窗口算法通常包括以下几个步骤：
-
初始化左右指针，表示窗口的左右边界。
-
移动右指针，扩大窗口，直到找到符合条件的窗口。
-
移动左指针，缩小窗口大小，直到不能再缩小为止。
-
在窗口移动的过程中，记录窗口的状态，例如最大值、最小值、子串长度等等。
-
返回窗口记录的结果。
可解决问题
滑动窗口算法可以用于解决一些数组和字符串相关的问题，例如：
找到最长的连续子数组或子字符串：可以使用滑动窗口算法来寻找最长的连续子数组或子字符串。在遍历数组或字符串时，我们可以维护一个窗口，通过移动窗口来寻找最长的连续子数组或子字符串。
找到满足某些条件的子数组或子字符串：可以使用滑动窗口算法来寻找满足某些条件的子数组或子字符串。在遍历数组或字符串时，我们可以维护一个窗口，通过移动窗口来寻找满足某些条件的子数组或子字符串。
找到最小的覆盖子串：可以使用滑动窗口算法来寻找最小的覆盖子串。在遍历字符串时，我们可以维护一个窗口，通过移动窗口来寻找最小的覆盖子串。
找到无重复字符的最长子串：可以使用滑动窗口算法来寻找无重复字符的最长子串。在遍历字符串时，我们可以维护一个窗口，通过移动窗口来寻找无重复字符的最长子串。
滑动窗口算法通常适用于处理数组和字符串问题，而且要求问题可以通过窗口内的元素来计算得出。此外，滑动窗口算法通常可以将时间复杂度优化到线性，因此在处理大规模数据时具有很好的效率。
应用
下面，我将通过两道简单题目来演示滑动窗口算法的应用。
题目一：最小覆盖子串
给定两个字符串 S 和 T，求 S 中包含 T 所有字符的最短子串。
示例：
输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"
题目解读：
我们可以维护两个指针 left 和 right，表示当前窗口的左右边界。初始时，左指针和右指针都指向字符串 S 的第一个字符。我们先移动右指针，直到找到包含字符串 T 的所有字符的子串。然后，我们移动左指针，缩小窗口大小，直到不能再缩小为止。在这个过程中，我们记录窗口的最小长度，并记录最小子串的起始位置。最后返回最小子串。
代码
public String minWindow(String s, String t) { int[] hash = new int[256];//ASCII 字符集共包含256个字符，因此使用长度为256的数组来记录窗口中每个字符出现的次数。 for (char c : t.toCharArray()) { hash[c]++; } int left = 0, right = 0, count = t.length(), start = 0, len = Integer.MAX_VALUE; while (right < s.length()) { if (hash[s.charAt(right)] > 0) { count--; } hash[s.charAt(right)]--; right++; while (count == 0) { if (right - left < len) { len = right - left; start = left; } if (hash[s.charAt(left)] == 0) { count++; } hash[s.charAt(left)]++; left++; } } return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);}题目二：长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：nums = [2,3,1,2,4,3], target = 7
输出：2
题目解读
我们可以维护两个指针 left 和 right，表示当前窗口的左右边界。初始时，左指针和右指针都指向数组的第一个元素。我们先移动右指针，直到窗口内的元素之和大于等于 target。然后，我们移动左指针，缩小窗口大小，直到不能再缩小为止。在这个过程中，我们记录窗口的最小长度，并更新最小长度的值。最后，返回最小长度。
代码
public int minSubArrayLen(int target, int[] nums) { int left = 0, right = 0, sum = 0, len = Integer.MAX_VALUE; while (right < nums.length) { sum += nums[right]; while (sum >= target) { len = Math.min(len, right - left + 1); sum -= nums[left]; left++; } right++; } return len == Integer.MAX_VALUE ? 0 : len;}滑动算法窗口的优缺点
优点：
- 时间复杂度较低：滑动窗口算法的时间复杂度通常是O(n)，因为它只需要遍历一次原数组。
- 空间复杂度较低：滑动窗口算法通常只需要使用常数级别的额外空间。
- 简单易懂：滑动窗口算法的思路比较简单，容易理解和实现。
缺点：
- 无法解决所有子串问题：滑动窗口算法只适用于解决一些特定类型的子串问题，无法解决所有子串问题。
- 可能存在重复计算：在一些情况下，滑动窗口算法可能会对同一段区间进行重复计算，导致效率降低。
- 可能存在局限性：滑动窗口算法有些场景下可能无法得到最优解，需要结合其他算法进行优化。
来源地址：https://blog.csdn.net/m0_63951142/article/details/130671127
