算法3 — 滑动窗口（python）

📣 前言：

可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

🌞 基本思想：

其基本思想总结如下：

• 设置左left、右端点right都为初始位置,left,right=0,0；
• 保持左端点不变，右端点向右移动 right += 1，直到子字符串满足要求，找到一个满足要求的子串；
• 此时保持右端点不变，收缩左端点left += 1，判断长度减小后，子串是否依然满足条件，如果满足，继续收缩左端点，直到不能收缩左端点为止；
• 判断左端点停止收缩时的子串与之前的子串，谁更符合条件（长度、最小、和最大等），则更新结果；
• 结果更新之后，此时left += 1，不满足条件，则继续向右移动右端点，继续寻找符合条件的子串。然后重复步骤2-4，直到遍历完整个字符串S。

📕 代码示例：

将上述思想进行编码实现，其伪代码如下：

class Solution:
    def function_name(self,XX,YY,...):  ##根据需求定义函数名称，变量 XX,YY根据需求增加，一般为要遍历搜索的字符串，和指定的字符串
        # Step 1: 定义需要维护的变量, 本题求最大长度，所以需要定义max_len, 该题又涉及去重，因此还需要一个哈希表
        x, y = ..., ..
        
        L = len(XX)  ## 要求全部遍历的字符串长度
        
        ## step2 初始化左右端点
        left,end = 0,0
       
        ## step3 开始遍历，不断移动右端点
        for right in range(L):
            x = new_x  # 得到右端点所在位置的字符
            if condition:  # 此条件有些需要，有些不需要
                hasp_ch = new_y
                
        '''
            ------------- 下面是两种情况，读者请根据题意二选1 -------------
            '''
            # Step 4 - 情况1 --- 长度固定
            # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 
            # 如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, 
            # 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 
            if 窗口长度达到了限定长度:
                # 更新 (部分或所有) 维护变量 
                # 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变

            # Step 4 - 情况2 --- 长度可变:
            # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while 不合法:
                # 更新 (部分或所有) 维护变量 
                # 不断移动窗口左指针直到窗口再次合法

        # Step 5: 返回答案
        return ...

🚩 例子应用：

利用上述伪代码进行例题展示

1️⃣ 例题1

76. 最小覆盖子串
    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”

示例 2：
输入：s = “a”, t = “a”
输出：“a”

示例 3:
输入: s = “a”, t = “aa”

输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

按步骤进行求解：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """1. 初始化变量"""
        hasp_s,valid_ch = {}, 0  # 验证window是否满足hasp_t条件，valid表示满足条件的字符个数
        
        """将指定字符串存在哈希表中更利于比较"""
        hasp_t = {}
        for char in t:
            hasp_t[char] = hasp_t.get(char,0)+1
        
        """计算需要遍历字符串长度"""
        length = len(s)+1
		
	    """2.左右端点初始值"""
        start,end = 0,0  ##左右端点初始值
        
        """3.开始遍历，更新变量"""
        while end < len(s):
            char = s[end]
            end += 1  #更新右端点
            if char in hasp_t:  ### 判断该字符是否在串T中，在，在增加到hasp_s中  
                hasp_s[char] = hasp_s.get(char,0) + 1
                if hasp_s[char] ==  hasp_t[char]:  ##判断值是否相等，相等，valid_ch增加1
                    valid_ch += 1
            
            """4.判断条件 固定长度"""
            while valid_ch == len(hasp_t):
                if end - start < length:  ## 优化结果，找到最小的子串
                    left = start
                    length = end - start  ## 现在子串的长度
                d = s[start]
                start += 1   #更新左端点
                if d in hasp_t: #如果左端点在字符串t中，判断是否值一致，纸一样都-1
                    if hasp_s[d] == hasp_t[d]:  # 有效子串valid_ch-1
                        valid_ch -= 1
                    hasp_s[d] -= 1
        if length != len(s)+1:
            res = s[left:left+length] 
        else:
            res = ""

        return res

2️⃣ 例题2

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

注意

子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]

示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]

提示：

1 <= s.length <= 104
s 由小写英文字母组成
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 由小写英文字母组成

按步骤进行求解：

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
    """1.初始化变量"""
    res, hasp_ch = 0,{}  ## 存放负荷要求的子串开头位置索引
    """2.左右端点初始化"""
    start,end=0
    """计算遍历字符串长度"""
    L = len(s)
    LW = len(words)
    first_w = len(words[0]) #计算每个单词的长度，因为单词的长度都相同
    """需将单词存放到哈希表中便于比较"""
    hasp_words = {} 
    for ch_w in words:
    	hasp_words[ch_w] = hasp_words.get(ch_w,0) + 1
    
    """3.开始遍历"""
    for start in range(L-len(words)+1):
        hasp_ch = {}
        for j in range(start,start+LW,first_w): ## 遍历相同长度的字符是否包含单词
        	char_s = s[j:j+first_w]
        	hasp_ch[char_s] = hashmap.get(char_s,0) + 1  ##存放中的字符到哈希表中
        
        """4.判断，固定长度"""
        if hasp_ch == hasp_words:  ## 子串与单词相同
        	res.append(start)  ## 保留起始索引
   return res

3️⃣ 例题3

209. 长度最小的子数组
     给定一个含有 n 个正整数的数组和一个正整数 target 。
     找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

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

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

按步骤进行求解：

## 长度最小的子数组
class Solution:
    def minSubArrayLen(self, target: int, nums: list) -> int:
        """计算遍历长度"""
        L = len(nums)
        
        """1.初始化变量"""
        min_l,sum_targe = math.inf,0
        
        """左右端点初始化"""
        start,end = 0,0
        
        """3.遍历字符，移动右端点"""
        for end in range(L):
            sum_targe += nums[end]

            """4.固定长度"""
            while sum_targe >= target:
                min_l = min(min_l,end-start+1)  # 找到最小
                sum_targe -= nums[start]
                start += 1

        if min_l == math.inf:
            return 0
        return min_l
                
target = 7 
nums = [2,3,1,2,4,3]    
S = Solution()
ss = S.minSubArrayLen(target,nums)
ss

4️⃣ 例题4

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

示例 1：
输入：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

示例 2：
输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

按步骤进行求解：

✒️ 开始使用的暴力法，但提交超过时间限制了，方法如下：

class Solution:
    def maxSlidingWindow(self, nums: list, k: int) ->list:
        L = len(nums)
        res = []
        for i in range(L-k+1):
            max_num = max(nums[i:i+k])
            res.append(max_num)
        return res
nums = [1,3,-1,-3,5,3,6,7]; k = 3  
S = Solution()
ss = S.maxSlidingWindow(nums,k)
ss

✒️ 然后更改为双端队列，方法如下：

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: list, k: int) ->list:
        L = len(nums)
        que = deque()
        res = []
        for i in range(L):
            if i == 0:
                que.append(i)
            else:
                if i - que[0] == k:
                    que.popleft()
                while que and nums[i] >= nums[que[-1]]:
                    que.pop()
                que.append(i)
            if i >= k -1:
                res.append(nums[que[0]])

        return res
nums = [1,3,-1,-3,5,3,6,7]; k = 3  
S = Solution()
ss = S.maxSlidingWindow(nums,k)
ss

5️⃣ 例题5

220. 存在重复元素 III
     给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
     如果存在则返回 true，不存在返回 false。

示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

按步骤进行求解：

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        bucket_all = {}     # 用列表保存桶
        for i in range(len(nums)):
            bucket_number = nums[i]//(t+1)
            if bucket_number in bucket_all:
                return True
            bucket_all[bucket_number] = nums[i]     # 放入桶中
            # 然后还要检查前一个桶和后一个桶有没有满足条件的
            if bucket_number-1 in bucket_all and abs(bucket_all[bucket_number-1] - nums[i]) <=t:
                return True
            if bucket_number+1 in bucket_all and abs(bucket_all[bucket_number+1] - nums[i]) <=t:
                return True
            
            if i >= k:  # 滑动窗口删除
                bucket_all.pop(nums[i-k]//(t+1))
        return False

6️⃣ 例题6

187. 重复的DNA序列
     DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。
     例如，“ACGAATTCCG” 是一个 DNA序列 。
     在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”,“CCCCCAAAAA”]

示例 2：
输入：s = “AAAAAAAAAAAAA”
输出：[“AAAAAAAAAA”]

提示：

0 <= s.length <= 105
s[i]==‘A’、‘C’、‘G’ or ‘T’

按步骤进行求解：

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        L = len(s)
        ## 构建初始变量
        hasp = {} 
        res = []
        
        """从左端点开始遍历，每次移动窗口为固定值10"""
        for i in range(L):
            char = s[i:i+10]
            """更新变量"""
            if char not in hasp:
                hasp[char] = hasp.get(char,0)+1
            else:
                hasp[char] += 1 
            if hasp[char] == 2: #注意等于2条件，避免元素重复,表示序列有两个
                res.append(char)
        return res

🍄 总结：

链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/yi-ge-mo-ban-miao-sha-10dao-zhong-deng-n-sb0x/
来源：力扣（LeetCode）