第13天打卡，附上學習鏈接

1 學習內(nèi)容

1.1 滑動窗口（Sliding Window）

滑動窗口，表示在給定的數(shù)組上維護一個固定長度或不定長度的窗口，可以對窗口進行滑動操作、縮放操作，以及維護最優(yōu)解操作?？梢詫⒒瑒哟翱诳醋魇强炻羔橀g的區(qū)間。

適用范圍：

• 固定長度窗口

• 不定長度窗口

1.2 固定長度窗口

實現(xiàn)步驟：

• （1）初始left=right=0，區(qū)間[left, right]稱為一個窗口；

• （2）當窗口未達到window_size固定大小時，不斷移動right，先將window_size個元素填入窗口中；

• （3）達到大小時，判斷是否滿足，滿足的情況下根據(jù)有要求更新最優(yōu)解，然后右移left，縮小窗口大??；

• （4）右移rght，在窗口中填充元素；重復，直到right達到數(shù)組尾端。

模板：

left = right = 0
while right < len(nums):
    window.append(nums[right])
    if right - left + 1 >= window_size:
        window.popleft()
        left += 1
    right += 1

示例習題1：1343 大小為K且平均值大于等于閾值的子數(shù)組數(shù)目 **

題目描述：給一個整數(shù)數(shù)組arr和兩個整數(shù)k和threshold。返回長度為k，且平均值大小等于threshold的子數(shù)組數(shù)目。 樣例1：輸入為arr=[2, 2, 2, 2, 5, 5, 5, 8]，k=3, threshold=4，輸出為3； 樣例2：輸入為arr=[1, 1, 1, 1, 1]，k=1，threshold=0，輸出為5； 樣例3：輸入為arr=[11, 13, 17, 23, 29, 31, 7, 5, 2, 3]，k=3，threshold=5，輸出為6； 樣例4：輸入為arr=[7, 7, 7, 7, 7, 7, 7]，k=7，threshold=7，輸出為1； 樣例5：輸入為arr=[4, 4, 4, 4]，k=4，threshold=1，輸出為1。

解題思路：固定長度為k的窗口，判斷均值和threshold，輸出計數(shù)結(jié)果。

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        left = right = 0
        win_sum = 0
        ans = 0
        while right < len(arr):
            win_sum += arr[right]
            if right - left + 1 >= k:
                if win_sum >= k * threshold:
                    ans += 1
                win_sum -= arr[left]
                left += 1
            right += 1
        return ans

1.4 不定長度窗口

實現(xiàn)步驟：

• （1）初始left=right=0，區(qū)間[left, right]稱為一個窗口；

• （2）將區(qū)間最右側(cè)的元素添加到窗口中，即window.append(s[right])；

• （3）然后right+1，增大窗口，直到窗口中的連續(xù)元素滿足要求；

• （4）此時，停止增加，開始window.pop(left)，left+1右移，縮小窗口；

• （5）窗口縮小到窗口中的連續(xù)元素不滿足要求；重復，直到right到達數(shù)組尾端。

模板：

left = right = 0
while right < len(nums):
    window.append(nums[right])
    while 需要縮小:
        window.popleft()
        left += 1
    right += 1  # 右側(cè)增大

示例習題1：0003 無重復字符的最長子串 **

題目描述：給一個字符串s，找出其中不含有重復字符的最長子串的長度。 樣例1：輸入為s="abcabcbb"，輸出為3； 樣例2：輸入為s="bbbbb"，輸出為1； 樣例3：輸入為s="pwwkew"，輸出為3； 樣例4：輸入為s=" "，輸出為0。

解題思路：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = right = 0
        window = dict()
        ans = 0
        
        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1
                
            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
            right += 1
        return ans

示例習題2：0209 長度最小的子數(shù)組 **

題目描述：給一個含有n個正整數(shù)的數(shù)組和一個正整數(shù)target，找出數(shù)組中滿足其和大于等于target的長度最小的連續(xù)子數(shù)組，并返回其長度。如果不存在符合條件的子數(shù)組，返回0。 樣例1：輸入為target=7，nums=[2, 3, 1, 2, 4, 3]，輸出為2； 樣例2：輸入為target=4，nums=[1, 4, 4]，輸出為1； 樣例3：輸入為target=11，nums=[1, 1, 1, 1, 1, 1, 1, 1]，輸出為0。

解題思路：先right+1擴大窗口，一旦和大于等于target，left-1縮小窗口并更新窗口長度的最小值，直到和小于target。重復，直到right>=len(nums)結(jié)束，輸出最小值即可。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        left = right = 0
        win_sum = 0
        
        while right < n:
            win_sum += nums[right]
            while win_sum >= target:
                ans = min(ans, right-left+1)
                win_sum -= nums[left]
                left += 1
            right += 1
        return ans if ans != n + 1 else 0

示例習題3：0713 乘積小于k的子數(shù)組 **

題目描述：給一個正整數(shù)數(shù)組nums和一個整數(shù)k，找出該數(shù)組內(nèi)乘積小于k的連續(xù)的子數(shù)組的個數(shù)。 樣例1：輸入為nums=[10, 5, 2, 6]，k=100，輸出,8； 樣例2：輸入為nums=[1, 2, 3]，k=0，輸出為0。

解題思路：同上，條件變?yōu)槌朔e，并且更新滿足條件的子數(shù)組個數(shù)。

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

2 練習題目

2.1 0674 最長連續(xù)遞增序列 **

題目描述：給出一個未經(jīng)排序的整數(shù)數(shù)組，找到最長且連續(xù)遞增的子序列，并返回該序列的長度。 樣例1：輸入為nums=[1, 3, 5, 4, 7]，輸出為3； 樣例2：輸入為nums=[2, 2, 2, 2, 2]，輸出為1。

解題思路： 更新最長的長度。

class Solution:
   def findLengthOfLCIS(self, nums: List[int]) -> int:
       left, right = 0, 1
       res = 1
       while right < len(nums):
           if nums[right] > nums[left]:
               while (right < len(nums)) and (nums[right] > nums[right - 1]):
                   res = max(res, right-left+1)
                   right += 1
           left = right
           right += 1
       
       return res

2.2 1004 最大連續(xù)1的個數(shù) III **

題目描述：給一個由若干0和1組成的數(shù)組A，最多可以將K個值從0變成1，返回僅包含1的最長（連續(xù)）子數(shù)組的長度。 樣例1：輸入為A=[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]，K=2，輸出6； 樣例2：輸入為A=[0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]，K=3，輸出為10。

解題思路：轉(zhuǎn)換題意為找出一個最長的子數(shù)組，其中最多允許有K個0。left和right初始值都為0，right右移，一旦為0，則窗口內(nèi)增加了一個0；當窗口內(nèi)的0的個數(shù)大于K時，left右移；滑動窗口長度的最大值就是所求。

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = 0
        left = right = 0
        cnt = 0
        while right < n:
            if nums[right] == 0:
                cnt += 1
            while cnt > k:
                if nums[left] == 0:
                    cnt -= 1
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res

2.3 0220 存在重復元素 III **

題目描述：一個整數(shù)數(shù)組nums和兩個整數(shù)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。

解題思路：待填空

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool: