先給出labuladong框架

/* 滑動窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是將移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
        ...

        

        // 判斷左側(cè)窗口是否要收縮
        while (window needs shrink) {
            // d 是將移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
            ...
        }
    }
}

下面有幾道典型的窗口題候生，前面幾道是很容易套這個(gè)模板的同眯。但是后面的兩道：求和和求乘積，并不是典型的窗口題唯鸭，或者說须蜗，有一點(diǎn)點(diǎn)小變化∧扛龋總體遵循的思想應(yīng)該是：1. 兩個(gè)while循環(huán)（或者第一個(gè)循環(huán)用for）2. 想清楚什么時(shí)候應(yīng)該收縮左邊窗口 3. 想清楚什么時(shí)候應(yīng)該往res返回結(jié)果里添加值明肮。

最小覆蓋子串

給你一個(gè)字符串 s 、一個(gè)字符串 t 缭付。返回 s 中涵蓋 t 所有字符的最小子串晤愧。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 蛉腌。

注意：如果 s 中存在這樣的子串官份，我們保證它是唯一的答案。

示例 1：

輸入：s = "ADOBECODEBANC", t = "ABC"
輸出："BANC"

示例 2：

輸入：s = "a", t = "a"
輸出："a"

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = collections.defaultdict(int) # 記錄t中字符出現(xiàn)次數(shù)
        window = collections.defaultdict(int) # 記錄窗口中響應(yīng)的字符出現(xiàn)的次數(shù)
        for c in t:
            need[c] += 1
        
        left,right = 0,0 # 初始窗口長度為0
        valid = 0 # 用于記錄window中t中字符是否出現(xiàn)完烙丛，比如：t='abc'舅巷，window='abd',valid就等于2.代表need中應(yīng)該出現(xiàn)的字符在window中才出現(xiàn)了兩個(gè)，還沒有出現(xiàn)完全

        # 記錄最小覆蓋子串的起始索引及長度
        start = 0
        length = float('inf')

        while right < len(s):
            c = s[right] # 即將加入window的字符c
            right += 1 # 右移窗口

            # 窗口內(nèi)數(shù)據(jù)的一系列更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]: # window中字符c出現(xiàn)的次數(shù)已經(jīng)達(dá)到need所需要的次數(shù)時(shí)河咽，valid進(jìn)行更新
                    valid += 1

            # 判斷窗口左側(cè)邊界是否要收縮
            while valid == len(need):
                # 在這里更新最小覆蓋子串
                if right-left < length:
                    start = left
                    length = right-left

                # d是將移出窗口的字符
                d = s[left]
                # 左移窗口
                left += 1
                # 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
                if d in need:
                    if window[d] == need[d]: # 這句話和下面的window[c]-=1不能反钠右，先判斷刪去的字符c的數(shù)量是不是滿足need的數(shù)量，如果滿足忘蟹，valid將減去1飒房。
                        valid -= 1
                    window[d] -= 1
        # 返回最小覆蓋子串
        if length == float('inf'):
            return ''
        else:
            return s[start:start+length]

字符串的排列

給定兩個(gè)字符串 s1 和 s2，寫一個(gè)函數(shù)來判斷 s2 是否包含 s1 的排列媚值。

換句話說狠毯，第一個(gè)字符串的排列之一是第二個(gè)字符串的 子串 。

示例 1：

輸入: s1 = "ab" s2 = "eidbaooo"
輸出: True
解釋: s2 包含 s1 的排列之一 ("ba").
示例 2：

輸入: s1= "ab" s2 = "eidboaoo"
輸出: False

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # 問題轉(zhuǎn)化為s2中是否存在一個(gè)子串褥芒，使得該子串包含s1中所有的元素嚼松，而且不包含其他字符。
        need = collections.defaultdict(int) # 記錄t中字符出現(xiàn)次數(shù)
        window = collections.defaultdict(int) # 記錄窗口中響應(yīng)的字符出現(xiàn)的次數(shù)
        for c in s1:
            need[c] += 1
        
        left,right = 0,0 # 初始窗口長度為0
        valid = 0 # 用于記錄window中t中字符是否出現(xiàn)完，比如：t='abc'献酗，window='abd',valid就等于2.代表need中應(yīng)該出現(xiàn)的字符在window中才出現(xiàn)了兩個(gè)寝受，還沒有出現(xiàn)完全

        # 記錄最小覆蓋子串的起始索引及長度
        start = 0
        length = float('inf')

        while right < len(s2):
            c = s2[right] # 即將加入window的字符c
            right += 1 # 右移窗口

            # 窗口內(nèi)數(shù)據(jù)的一系列更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]: # window中字符c出現(xiàn)的次數(shù)已經(jīng)達(dá)到need所需要的次數(shù)時(shí)，valid進(jìn)行更新
                    valid += 1

            # 判斷窗口左側(cè)邊界是否要收縮(當(dāng)窗口內(nèi)的字符數(shù)量大于該有的字符數(shù)量時(shí)罕偎，左邊需要收縮)
            while right-left >= len(s1):
                # 在這里判斷是否找到了合法子串
                if valid == len(need):
                    return True

                # d是將移出窗口的字符
                d = s2[left]
                # 左移窗口
                left += 1
                # 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
                if d in need:
                    if window[d] == need[d]: # 這句話和下面的window[c]-=1不能反很澄，先判斷刪去的字符c的數(shù)量是不是滿足need的數(shù)量，如果滿足颜及，valid將減去1甩苛。
                        valid -= 1
                    window[d] -= 1
                    
        return False

無重復(fù)字符的最長子串

給定一個(gè)字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度器予。

示例 1:

輸入: s = "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"浪藻，所以其長度為 3捐迫。
示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"乾翔，所以其長度為 1。
示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"施戴，所以其長度為 3反浓。
請注意，你的答案必須是 子串 的長度赞哗，"pwke" 是一個(gè)子序列雷则，不是子串。
示例 4:

輸入: s = ""
輸出: 0

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        max_length = 0
        window = collections.defaultdict(int)

        left,right = 0,0
    
        while right < len(s):
            c = s[right]
            right += 1
            window[c] += 1
            
            # 當(dāng)window中有重復(fù)字符的時(shí)候開始收縮左邊界
            while window[c] > 1: 
                d = s[left]
                left += 1
                window[d] -= 1
            
            max_length = max(max_length,right-left)
        
        return max_length

要在收縮窗口完成后更新 res肪笋，因?yàn)榇翱谑湛s的 while 條件是存在重復(fù)元素月劈。

至多包含K個(gè)不同字符的最長子串

給定一個(gè)字符串 s ，找出 至多 包含 k 個(gè)不同字符的最長子串 T藤乙。

示例 1:

輸入: s = "eceba", k = 2
輸出: 3
解釋: 則 T 為 "ece"猜揪，所以長度為 3。
示例 2:

輸入: s = "aa", k = 1
輸出: 2
解釋: 則 T 為 "aa"坛梁，所以長度為 2而姐。

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        max_length = 0 
        left,right = 0,0
        valid = 0
        window = collections.defaultdict(int)
        while right < len(s):
            c = s[right]
            right += 1
            
            if window[c] == 0:
                valid += 1
            window[c] += 1

            # 當(dāng)窗口內(nèi)字符串包含多于k個(gè)不同字符時(shí)，收縮窗口左邊邊界
            while valid > k :
                d = s[left]
                left += 1

                if window[d] == 1:
                    valid -= 1
                window[d] -= 1
            
            max_length = max(max_length,right-left)
        
        return max_length

438.找到字符串中的所有字母異位詞

給定兩個(gè)字符串 s 和 p划咐，找到 s 中所有 p 的 異位詞 的子串拴念，返回這些子串的起始索引。不考慮答案輸出的順序褐缠。

異位詞 指字母相同政鼠，但排列不同的字符串。

示例 1:

輸入: s = "cbaebabacd", p = "abc"
輸出: [0,6]
解釋:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的異位詞队魏。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的異位詞缔俄。
示例 2:

輸入: s = "abab", p = "ab"
輸出: [0,1,2]
解釋:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的異位詞。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的異位詞。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的異位詞俐载。

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        window = collections.defaultdict(int)
        need = collections.defaultdict(int)
        for ch in p:
            need[ch] += 1
        res = [] # 存儲最終返回結(jié)果蟹略，即各子串的起始index
        left,right= 0,0
        length = len(p) + 1
        valid = 0
        
        while right < len(s):
            # 準(zhǔn)備移入窗口的字符
            c = s[right]
            right += 1

            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid +=1
            
            # 判斷何時(shí)需要收縮左邊窗口邊界
            while right-left >= len(p):
                if valid == len(need):
                    res.append(left)
                # 即將擠出窗口的字符d
                d = s[left]
                left += 1
                
                if d in need:
                    if window[d] == need[d]:
                        valid -=1
                    window[d] -= 1
        
        return res

209. 長度最小的子數(shù)組

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。

找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] 遏佣，并返回其長度挖炬。如果不存在符合條件的子數(shù)組，返回 0 状婶。

示例 1：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組意敛。
示例 2：

輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：

輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        windows = defaultdict(int)
        left , right = 0,0

        n = len(nums)
        res = float('inf')
        s = 0
        while right < n:
            num = nums[right]
            
            s += num

            while s >= target:
                res = min(res,right-left+1)
                num = nums[left]
                left += 1               
                s -= num
            
            right += 1

        if res != float('inf') :
            return res
        else:
            return 0

731.乘積小于K的子數(shù)組

給定一個(gè)正整數(shù)數(shù)組 nums和整數(shù) k 。

請找出該數(shù)組內(nèi)乘積小于 k 的連續(xù)的子數(shù)組的個(gè)數(shù)膛虫。

示例 1:

輸入: nums = [10,5,2,6], k = 100
輸出: 8
解釋: 8個(gè)乘積小于100的子數(shù)組分別為: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]草姻。
需要注意的是 [10,5,2] 并不是乘積小于100的子數(shù)組。
示例 2:

輸入: nums = [1,2,3], k = 0
輸出: 0

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1: return 0
        res = 0
        left = 0
        right = 0
        s = 1
        while right < len(nums):
            num = nums[right]                      
            s = s * num
                       
            while s >= k :
                num = nums[left]
                s = s / num
                left += 1
                
            res += (right-left) + 1
            right += 1
               
        return res