关于数组指针的解法，有两种：

滑动窗口：指针同向移动；
双指针：指针相向移动。

它们都利用了问题本身的特点和目标函数的最值性进行「剪枝」。这期我们了解滑动窗口。

滑动窗口算法，利用左右指针维护窗口中的数据，窗口区间是左闭右开区间，[left,right)。

滑动窗口算法通用流程：

初始化：初始化左右指针，left, right = 0, 0；初始化窗口window={}，最初时window不包含数据；寻找可行解：不断扩大窗口的右边界，右指针right+=1，将新数据加入窗口，并检测此时窗口中的字串是否满足题目要求；优化可行解：当窗口包含的字串满足题目要求时，开始收缩窗口的左边界，left+=1，直至不再满足题目要求；滑动窗口过程中，注意数据的实时更新，找到保存结果的位置。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

1. 题目描述 - 最大连续 1 的个数 III

Question source

解题思路

用双指针记录窗口的起始位置，然后不断的移动窗口同时保证窗口内0的个数小于等于k，取最大的窗口数。

复杂度

时间复杂度：O(m)
空间复杂度：O(1)

Code

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        end, max_length, zero_count= 0, 0, 0 
        for i, num in enumerate(A):
            if num == 0:
                zero_count += 1
            if zero_count > K:
                while A[end] != 0:
                    end += 1
                if A[end] == 0:
                    end += 1
                    zero_count -= 1
            max_length = max(max_length, i-end+1)
        return max_length

类似题：lc 424 - 替换后的最长重复字符

Question source

该题与上题区别是：窗口内个数小于等于k的元素不是确定的0，而可能是任意的大写字母，所以我们要引入一个长度为 26 的数组维护每一个字符的出现次数。

解题思路

们可以枚举字符串中的每一个位置作为右端点，然后找到其最远的左端点的位置，满足该区间内除了出现次数最多的那一类字符之外，剩余的字符（即非最长重复字符）数量不超过 k 个。

这样我们可以想到使用双指针维护这些区间，每次右指针右移，如果区间仍然满足条件，那么左指针不移动，否则左指针至多右移一格，保证区间长度不减小。

虽然这样的操作会导致部分区间不符合条件，即该区间内非最长重复字符超过了 k 个。但是这样的区间也同样不可能对答案产生贡献。当我们右指针移动到尽头，左右指针对应的区间的长度必然对应一个长度最大的符合条件的区间。

每次区间右移，我们更新右移位置的字符出现的次数，然后尝试用它更新重复字符出现次数的历史最大值，最后我们使用该最大值计算出区间内非最长重复字符的数量--是否大于k，以此判断左指针是否需要右移即可[1]。

当滑动窗口不满足max_val + k < right - left + 1，left要右移一步（左指针需要右移）。

复杂度

时间复杂度： O(n)，其中 n 是字符串的长度。我们至多只需要遍历该字符串一次。
空间复杂度： O(∣Σ∣)，其中 ∣Σ∣ 是字符集的大小。我们需要存储每个大写英文字母的出现次数。

代码

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_val,end = 0 ,0
        num = [0] * 26
        for i in range(len(s)): 
            num[ord(s[i])-ord("A")] += 1 
            # 求窗口中曾出现某字母的最大次数
            # 计算某字母出现在某窗口中的最大次数，窗口长度只能增大或者不变（注意后面left指针只移动了0-1次）
            # 这样做的意义：我们求的是最长，如果找不到更长的维持长度不变返回结果不受影响 
            max_val = max(num[ord(s[i])-ord("A")],max_val)
            if max_val + k < i-end+1:
                num[ord(s[end])-ord("A")] -= 1 
                end += 1 
        return len(s) - end # 最后窗口的大小，便是可扩充的最大窗口
        # right - left在整个过程是非递减的。只要right 的值加进去不满足条件，left和right就一起右滑，因为长度小于right - left的区间就没必要考虑了，所以right - left一直保持为当前的最大值

答疑【汇总自官方题解评论区】

为什么维护的是历史最大值啊？历史最大值所对应的字母不是不一定全都出现在当前窗口里吗？

答：历史最大值是这样的，比如一个子串k=2,然后有一段他的最大重复个数maxn是4，这时候他的长度是6，然后移动滑动窗口到另一段，如果这一串的最大重复个数小于4，那一定不会得到一个大于6的结果，所以记录历史最大值是可以了

从k的角度如何观察窗口大小？

答：维护历史最大值的原因：窗口从根本来说是只增不减的：

如果k够用来替换的话，right右移1步，窗口变大（当前维护的最大值变大，不消耗k；当前维护的最大值不变，将消耗k）；

如果k不够用来替换的话，left和right都右移一步，窗口不变（我们已经不关心比当前小的情况了）。

从这个角度来说，也不难理解最后答案是right-left（最后窗口的大小，可扩充的最大窗口）。

2 lc 76 - 最小覆盖子串

题目来源

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

难度：困难

解题思路

right 一直往前走，走到 [left, right] 包含 T 里所有的字母； right 和 left 同方向；小技巧：用哈希表或者数组统计不同字母的个数，这样可以保证复杂度最低，具体使用「数组」还是「哈希表」需要根据具体情况具体分析。

重要的几点： 1. t中可以有重复元素，而所有这些元素都需要在窗口中；——》只能利用哈希表来统计每个元素出现几次了； 2. 开篇的总结中，提到的并检测此时窗口中的字串是否满足题目要求。题目要求在下面代码中为：window哈希表中每个元素的values大于或等于need哈希表中对应元素的values。

复杂度

时间复杂度：O(C*|s|+|t|)。
- 最坏情况下，左右指针分别遍历一边字符串s，每次移动左指针或右指针，都对应着一次在need中查询字符及window字典的数据更新，设C为字符集的字符个数，则时间复杂度为O(C|s|) + O(C|s|) -> O(C*|s|)；
- 最开始初始化时遍历了一次字符串t，时间复杂度O(|t|)；
- 所以总时间复杂度：O(C*|s|+|t|)
空间复杂度：O(C)，取决于两个字典need和window，C为字符集的字符个数。

代码

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if s == t : return s
        if len(s)<len(t): return ""
        i,j = 0,0 
        need = dict()
        for c in t:
            need[c] = need.get(c, 0) + 1    # need = {字符:出现次数} 

        min_len = float('inf')
        cur_len = float('inf')
        cur,res = "",""
        window = dict()
        while j<= len(s)-1:  
            if s[j] in need:
                window[s[j]]=window.get(s[j],0)+1
            
            while self.match(window, need):
                while s[i] not in need: 
                    i += 1
                # print(i)
                cur_len = j-i
                cur = s[i:j+1]
                # print(cur)
                if cur_len< min_len:
                    min_len = cur_len
                    res = cur
                # print(res)
                window[s[i]] -= 1
                if window[s[i]] == 0:  del window[s[i]] 
                
                i += 1
                 
            # print(s[i:j+1])
            # print(window)
            # print(need)
            j += 1
            # print(hashmap,i)
        return res
    
    def match(self, window, need):
        if len(window) == len(need):
            for k,v in (window.items()):
                if v < need[k]:
                    return False
            return True
        else:
            return False

2 lc 697 - 数组的度

题目来源

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

难度：中等

解题思路

使用 left 和 right 分别保存了每个元素在数组中第一次出现的位置和最后一次出现的位置；使用 counter 保存每个元素出现的次数。
数组的度 degree 等于 counter.values() 的最大值；
对counter再次遍历：
- 如果元素 k 出现的次数等于 degree，则找出元素 k 最后一次出现的位置和第一次出现的位置，计算两者之差+1，即为子数组长度。
- 对所有出现次数等于 degree 的子数组的最短长度，取 min[3]。

复杂度

时间复杂度：O(n)。因为对数组遍历了一遍，对counter 遍历了两遍。
空间复杂度：O(n)。因为 counter 在最坏情况下会跟 nums 的元素个数相等

代码

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        left,right = dict(),dict()
        counter = collections.Counter()
        for i,num in enumerate(nums):
            if num not in left:
                left[num] = i
            right[num] = i
            counter[num] += 1
        degree = max(counter.values())
        min_len = len(nums)
        for k,v in counter.items():
            if v == degree:
                min_len = min(min_len,right[k]-left[k]+1)
        return min_len

参考

[1] LeetCode-Solution. https://leetcode-cn.com/problems/longest-repeating-character-replacement/solution/ti-huan-hou-de-zui-chang-zhong-fu-zi-fu-n6aza/ [2] jue-qiang-zha-zha. 76. https://leetcode-cn.com/problems/minimum-window-substring/solution/76-zui-xiao-fu-gai-zi-chuan-hua-dong-chu-9ju0/ [3] https://leetcode-cn.com/problems/degree-of-an-array/solution/xiang-xi-fen-xi-ti-yi-yu-si-lu-jian-ji-d-nvdy/

算法 | 滑动窗口专题

1. 题目描述 - 最大连续 1 的个数 III

解题思路

复杂度

Code

类似题：lc 424 - 替换后的最长重复字符

解题思路

复杂度

代码

答疑【汇总自官方题解评论区】

2 lc 76 - 最小覆盖子串

解题思路

复杂度

代码

2 lc 697 - 数组的度

解题思路

复杂度

代码

相关题目

参考