算法训练之 -- 滑动窗口

滑动窗口

1. 思路

​ 题目：给定一个含有n个正整数的数组和一个正整数s，找出该数组中满足其和≥s的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回0。长度最小的子数组

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路：所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

滑动窗口的方法： i为滑动窗口的终止位置，j为滑动窗口的起始位置，Sum记录当前j->i连续子数组的和，i-j+1为当前连续子数组的长度。

PS：滑动窗口最重要的是判断 左边的 指针什么时候开始滑动

2. 解法

Python：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = Sum = 0
        Len =  float("inf")
        for i in range(len(nums)):
            Sum += nums[i]  # Sum为当前子数组的和
            while Sum >= target: 
                Len = min(Len, i - l + 1)    # 有最小 最大要求 就需要进行比较
                Sum -= nums[l]              # Sum减去当前子数组的起始元素
                l += 1
        Len = 0 if Len == float("inf") else Len # 如果Len没有被赋值，说明没有符合条件的子数组，返回0
        return Len

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l=0, r = 0, sum = 0, len = INT_MAX;
        for(r=0; r < nums.size(); r++){ //滑动窗口
            sum += nums[r];
            while(sum >= target){
                len = min(len, r-l+1); //记录最小长度
                sum -= nums[l++]; //缩小窗口
            } 
        }
        return len == INT_MAX ? 0 : len;
    }
};

3. 变种

☆☆（1）题目：你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

  • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。904. 水果成篮 - 力扣（LeetCode）

思路：本题等价于 在一个窗口中找到最长的 只包含两个不同元素的最长子串序列（不同的元素不需要连续）

使用滑动窗口解决本题，left 和 right 分别表示满足要求的窗口的左右边界，同时我们使用哈希表存储这个窗口内的数以及出现的次数。

  • 每次将 right 移动一个位置，并将 fruits[right] 加入哈希表。

  • 如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动 left，并将 fruits[left]从哈希表中移除，直到哈希表满足要求为止。

  • 需要注意的是，将 fruits[left] 从哈希表中逐步减少后，如果 fruits[left]在哈希表中的出现次数减少为0，需要将对应的键值对从哈希表中移除。

PS：滑动窗口的重点在于如何 创建窗口 和 更新窗口

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        cnt = Counter() 			# 用字典存储哈希表
        l = maxlen = 0
        for r in range(len(fruits)):
            cnt[fruits[r]] += 1		# 创建一个窗口
            while len(cnt) > 2:		# 缩小窗口 从而更新窗口
                cnt[fruits[l]] -= 1
                if cnt[fruits[l]] == 0:
                    cnt.pop(fruits[l])
                l += 1

            maxlen = max(maxlen, r-l+1)
        
        return maxlen

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int l=0, maxlen = 0;
        unordered_map<int, int> cnt;    // 创建map字典

        for(int r=0; r<fruits.size(); r++){
            cnt[fruits[r]]++;           // 创建窗口
            while(cnt.size() > 2){
                auto it = cnt.find(fruits[l]);  // 在字典中查找元素
                it->second--;       
                if(it->second == 0)     // 破坏窗口
                    cnt.erase(it);
            l++;                        // 窗口左移缩小 从而更新
            }   
            maxlen = max(maxlen, r-l+1);
        }
        return maxlen;
    }
};

☆☆☆ (2) 题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。76. 最小覆盖子串 - 力扣（LeetCode）

思路：用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最小值就是要求的结果。

  • 不断增加j使滑动窗口增大，直到窗口包含了T的所有元素
  • 不断增加i使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值
  • 让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了字符串S范围。

PS：思路讲解本题思路讲解

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # cnt = Counter(t)	# 使用下面的字典方法速度更快
        cnt = collections.defaultdict(int)	# 使用字典存储 t 中的元素及其个数
        for c in t:
            cnt[c] += 1
        cntLen = len(t)
        left = 0
        ans = (0, float('inf'))
        # for right in range(len(s)):	# 使用enum函数直接取元素， 比通过索引查询字符串中的元素要快
        #     c = s[right]
        for idx, c in enumerate(s):		# 从 s 字符串中取元素
            if cnt[c] > 0:
                cntLen -= 1				# 如果当前元素是 t 中元素， 长度 -1
            cnt[c] -= 1					# 更新字典，字典中对应的 c 元素 -1（如果在t中不存在，值则为-1）
            if cntLen == 0:				# 如果 t 总长度为0， 则说明当前窗口中已经包含了所有的 t 中的元素，准备缩小窗口
                while True:
                    if cnt[s[left]] == 0:	# 如果当前元素为 t 中的元素，跳出循环（窗口中需要包含 t 中的元素）
                        break
                    cnt[s[left]] += 1		# 更新字典，当前元素值 +1
                    left += 1				# 缩小窗口
                if idx - left < ans[1] - ans[0]:	# 进行比较，更新最小子串 
                    ans = (left, idx)
                cnt[s[left]] += 1			# 下面这三行是因为 s[left] in t，当前窗口的第一个元素当好在 t 中
                cntLen += 1					# 从上面的 if 中 break 出来了，所以需要对其进行 +1 操作		
                left += 1					# 同时 t 的总长度就也需要对应的 +1，从而使得窗口继续滑动
        return '' if ans[1] > len(s) else s[ans[0]:ans[1]+1]

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> cnt;
        for(const char& c : t){
            cnt[c]++;
        }
        int cntLen = t.length();
        int left = 0, start = 0, end = INT_MAX;
        for(int right=0; right<s.length(); right++){
            if(cnt[s[right]] > 0)
                cntLen--;
            cnt[s[right]]--;
            if(cntLen == 0){
                while(true){
                    if(cnt[s[left]] == 0)
                        break;
                    cnt[s[left++]]++;
                }
                if(right - left + 1 < end){
                    start = left
                    end = right - left + 1;
                }
                cnt[s[left++]]++;
                cntLen++;
            }
        }
        return end == INT_MAX ? "" : s.substr(start, end);  // substr(start_idx, len) 开始位置，截取长度
    }
};

(3) 题目：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。3. 无重复字符的最长子串 - 力扣（LeetCode）

思路：滑动窗口 + 哈希表，哈希表的表示可以使用字典和集合，使用集合的速度比使用字典的速度要快

解法一：

  • 哈希表 dicdicdic 统计： 指针 j 遍历字符 s ，哈希表统计字符 s[j] 最后一次出现的索引 。

  • 更新左指针 i： 根据上轮左指针 i 和 dic[s[j]] ，每轮更新左边界 i ，保证区间 [i+1,j][i + 1, j][i+1,j] 内无重复字符且最大。\(i=max⁡(dic[s[j]],i)\)

  • 更新结果 res ： 取上轮 res 和本轮双指针区间 [i+1,j] 的宽度（即 j−i）中的最大值。\(res=max⁡(res,j−i)\)

解法二：

  • 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」，而右指针即为\(r_k\)

  • 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

  • 在枚举结束后，我们找到的最长的子串的长度即为答案。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 解法一：
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic, res, i = {}, 0, -1
        n = len(s)
        for j in range(n):
            if s[j] in dic:
                i = max(dic[s[j]], i)	# 找到第二个相同字符的索引
            dic[s[j]] = j           # 字典的值为当前字符的索引
            res = max(res, j - i)
        return res
    
 # 解法二：
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0 # 也可以从0开始
        for i in range(n):
            if i != 0:   # 左指针向右移动一格，移除一个字符， 这个时候为遇到了相同字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ: # 不断地移动右指针，扩大窗口，直到遇到相同字符
                occ.add(s[rk + 1])
                rk += 1
            ans = max(ans, rk - i + 1)  # 第 i 到 rk 个字符是一个极长的无重复字符子串
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合，记录每个字符是否出现过
        unordered_set<char> occ;
        int n = s.size();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        // 枚举左指针的位置，初始值隐性地表示为 -1
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
                // 不断地移动右指针
                occ.insert(s[rk + 1]);
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

(4) 题目:给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。567. 字符串的排列 - 力扣（LeetCode）

思路：题解 滑动窗口 + 字典 Or 数组 窗口固定

  • 分析一：题目要求 s1 的排列之一是 s2 的一个子串。而子串必须是连续的，所以要求的 s2 子串的长度跟 s1 长度必须相等。
  • 分析二： 那么我们有必要把 s1 的每个排列都求出来吗？当然不用。如果字符串 a 是 b 的一个排列，那么当且仅当它们两者中的每个字符的个数都必须完全相等。
    • 使用一个长度和 s1 长度相等的固定窗口大小的滑动窗口，在 s2 上面从左向右滑动，判断 s2 在滑动窗口内的每个字符出现的个数是否跟 s1 每个字符出现次数完全相等。
    • 定义 counter1 是对 s1 内字符出现的个数的统计，定义 counter2 是对 s2 内字符出现的个数的统计。在窗口每次右移的时候，需要把右边新加入窗口的字符个数在 counter2 中加 1，把左边移出窗口的字符的个数减 1。如果 counter1 == counter2 ，那么说明窗口内的子串是 s1 的一个排列，返回 True；如果窗口已经把 s2 遍历完了仍然没有找到满足条件的排列，返回 False。

PS：本题中的 counter 可以用字典，也可以用数组来实现。用字典的时候，需要注意：如果移除 left 元素后，若 counter2[s2[left]] == 0 那么需要从字典中删除 s2[left] 这个key。因为 {"a":0, "b":1} 和 {"b":1} 是不等的。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        # 统计 s1 中每个字符出现的次数
        counter1 = collections.Counter(s1)
        N = len(s2)
        # 定义滑动窗口的范围是 [left, right]，闭区间，长度与s1相等
        left = 0
        right = len(s1) - 1
        # 统计窗口s2[left, right - 1]内的元素出现的次数
        counter2 = collections.Counter(s2[0:right])
        while right < N:
            # 把 right 位置的元素放到 counter2 中
            counter2[s2[right]] += 1
            # 如果滑动窗口内各个元素出现的次数跟 s1 的元素出现次数完全一致，返回 True
            if counter1 == counter2:
                return True
            # 窗口向右移动前，把当前 left 位置的元素出现次数 - 1
            counter2[s2[left]] -= 1
            # 如果当前 left 位置的元素出现次数为 0， 需要从字典中删除，否则这个出现次数为 0 的元素会影响两 counter 之间的比较
            if counter2[s2[left]] == 0:
                del counter2[s2[left]]
            # 窗口向右移动
            left += 1
            right += 1
        return False

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 使用数组来存储
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int len1 = s1.length(), len2 = s2.length();

        if(len1 > len2)		// 使用数组存储需要注意判断子数组的长度是不是大于父数组的长度
            return false;

        vector<int> cnt1(26), cnt2(26);
        for(int i=0; i<len1; i++){	// 存储 s1的元素 以及 s2 对应s1的元素
            cnt1[s1[i] - 'a']++;
            cnt2[s2[i] - 'a']++;
        }
        if(cnt1 == cnt2)			// 判断是否相等
            return true;
        for(int i=len1; i<len2; i++){	// 移动窗口， 窗口大小不变
            cnt2[s2[i] - 'a']++;		// 一进
            cnt2[s2[i-len1] - 'a']--;	// 一出
            if(cnt1 == cnt2)
                return true;
        }
        return false;
    }
};

(5) 题目：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

思路：和（4）的解法一样，固定窗口，一进一出

根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 使用字典
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        len_p = len(p)
        left, right, ans = 0, len_p, []
        cnt_p = collections.defaultdict(int)
        cnt_s = collections.defaultdict(int)
        for c in p:			# 初始化 p 的字典
            cnt_p[c] += 1
        for c in s[0:right]:	# 初始化 s 的字典，此时只需要和 p 的长度相同
            cnt_s[c] += 1
        if cnt_p == cnt_s:		# 先判断一波是否相等，方便后续窗口移动
            ans.append(left)
        while right < len(s):	# 开始移动窗口 一进一出 窗口大小固定
            cnt_s[s[right]] += 1
            cnt_s[s[left]] -= 1
            if cnt_s[s[left]] == 0:	# ps: 如果元素为0了，则需要将其删除
                del cnt_s[s[left]]
            left += 1
            right += 1
            if cnt_p == cnt_s:	# 判断是否相等
                ans.append(left)
        return ans

 # 使用数组
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len, p_len = len(s), len(p)
        
        if s_len < p_len:	# 使用数组则需要进行长度比较
            return []

        ans = []
        s_count = [0] * 26	# 方法一样， 只是将字母通过一个长度为26的数组进行保存
        p_count = [0] * 26
        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1

        if s_count == p_count:
            ans.append(0)

        for i in range(s_len - p_len):
            s_count[ord(s[i]) - 97] -= 1
            s_count[ord(s[i + p_len]) - 97] += 1
            
            if s_count == p_count:
                ans.append(i + 1)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int len_p = p.size(), len_s = s.size();
        if(len_p > len_s)
            return vector<int>();
        vector<int> ans;
        vector<int> list_p(26);
        vector<int> list_s(26);
        for(int i=0; i<len_p; i++){
            list_p[p[i] - 'a']++;
            list_s[s[i] - 'a']++;
        }
        if(list_p == list_s)
            ans.emplace_back(0);
        for(int i=len_p; i<len_s; i++){
            list_s[s[i] - 'a']++;
            list_s[s[i-len_p] - 'a']--;
            if(list_p==list_s)
                ans.emplace_back(i-len_p+1);
        }
        return ans;
    }
};
算法
#刷题
算法训练之 -- 滑动窗口
http://seulqxq.top/posts/60655/
作者
SeulQxQ
发布于
2023年12月19日
许可协议