第13天打卡，附上学习链接
1 学习内容
1.1 滑动窗口（Sliding Window）
滑动窗口，表示在给定的数组上维护一个固定长度或不定长度的窗口，可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。可以将滑动窗口看作是快慢指针间的区间。
适用范围：
固定长度窗口
不定长度窗口
1.2 固定长度窗口
实现步骤：
（1）初始left=right=0，区间[left, right]称为一个窗口；
（2）当窗口未达到window_size固定大小时，不断移动right，先将window_size个元素填入窗口中；
（3）达到大小时，判断是否满足，满足的情况下根据有要求更新最优解，然后右移left，缩小窗口大小；
（4）右移rght，在窗口中填充元素；重复，直到right达到数组尾端。
模板：
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且平均值大于等于阈值的子数组数目 **
题目描述：给一个整数数组arr和两个整数k和threshold。返回长度为k，且平均值大小等于threshold的子数组数目。 样例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，输出计数结果。
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 不定长度窗口
实现步骤：
（1）初始left=right=0，区间[left, right]称为一个窗口；
（2）将区间最右侧的元素添加到窗口中，即window.append(s[right])；
（3）然后right+1，增大窗口，直到窗口中的连续元素满足要求；
（4）此时，停止增加，开始window.pop(left)，left+1右移，缩小窗口；
（5）窗口缩小到窗口中的连续元素不满足要求；重复，直到right到达数组尾端。
模板：
left = right = 0
while right < len(nums):
window.append(nums[right])
while 需要缩小:
window.popleft()
left += 1
right += 1 # 右侧增大
示例习题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 长度最小的子数组 **
题目描述：给一个含有n个正整数的数组和一个正整数target，找出数组中满足其和大于等于target的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回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)结束，输出最小值即可。
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的子数组 **
题目描述：给一个正整数数组nums和一个整数k，找出该数组内乘积小于k的连续的子数组的个数。 样例1：输入为nums=[10, 5, 2, 6]，k=100，输出,8； 样例2：输入为nums=[1, 2, 3]，k=0，输出为0。
解题思路：同上，条件变为乘积，并且更新满足条件的子数组个数。
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 最长连续递增序列 **
题目描述：给出一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。 样例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 最大连续1的个数 III **
题目描述：给一个由若干0和1组成的数组A，最多可以将K个值从0变成1，返回仅包含1的最长（连续）子数组的长度。 样例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。
解题思路：转换题意为找出一个最长的子数组，其中最多允许有K个0。left和right初始值都为0，right右移，一旦为0，则窗口内增加了一个0；当窗口内的0的个数大于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 **
题目描述：一个整数数组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。
解题思路：待填空
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
