数组 滑动窗口

1.固定长度滑动窗口固定长度滑动窗口算法Fixed Length Sliding Window在数组 / 字符串上维护一个长度固定的窗口通过不断向右滑动窗口实时更新窗口内的数据并根据题目要求动态维护最优解。定义两个指针 leftleft 和 rightright初始都指向序列起始位置left0,right0left0,right0区间 [left,right][left,right] 表示当前窗口。不断右移 rightright将元素加入窗口如window.append(nums[right])。当窗口长度达到 window_sizewindow_size即right - left 1 window_size时判断窗口内元素是否满足题目要求如果满足则更新答案。右移 leftleftleft 1保持窗口长度不变。重复上述过程直到 rightright 遍历完整个数组。固定长度滑动窗口代码模板left 0 # 窗口左边界 right 0 # 窗口右边界 while right len(nums): # 将当前元素加入窗口 window.append(nums[right]) # 判断当前窗口长度是否达到 window_size if right - left 1 window_size: # 在窗口长度达到要求时进行答案的统计或更新 # ... 这里根据题目需求维护/更新答案 # 移除窗口最左侧元素窗口向右滑动 window.popleft() left 1 # 左指针右移缩小窗口长度保持窗口长度为 window_size # 右指针右移扩大窗口 right 1例题1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣LeetCode给你一个整数数组arr和两个整数k和threshold。请你返回长度为k且平均值大于等于threshold的子数组数目。示例 1输入arr [2,2,2,2,5,5,5,8], k 3, threshold 4输出3解释子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 45 和 6 。其他长度为 3 的子数组的平均值都小于 4 threshold 的值)。public class Solution { public int NumOfSubarrays(int[] arr, int k, int threshold) { int left 0 ; int right 0; float sum 0f; int ans 0; while(rightarr.Length) { sumarr[right]; if((right-left1)k) { if((sum/k)threshold) { ans; } sum-arr[left]; left; } right; } return ans; } }2. 不定长度滑动窗口不定长滑动窗口Sliding Window在数组 / 字符串上用两个指针动态维护一个可变长度的窗口通过左右移动指针灵活调整窗口范围实时维护最优解。定义左右指针 leftleft、rightright初始都为 00区间 [left,right][left,right] 表示当前窗口。将 s[right]s[right] 加入窗口如window.add(s[right])然后 right1right1扩大窗口。当窗口不满足条件时不断移除 s[left]s[left]如window.popleft()并 left1left1缩小窗口直到重新满足条件。重复上述过程直到 rightright 遍历完整个序列。不定长度滑动窗口代码模板# 初始化左右指针均指向数组起始位置 left 0 right 0 # 主循环右指针遍历整个数组 while right len(nums): # 将当前右指针指向的元素加入窗口 window.append(nums[right]) # 当窗口不满足题目要求时缩小窗口移动左指针 while 窗口需要缩小: # 此处可根据题意维护/更新答案 window.popleft() # 移除左边界元素 left 1 # 左指针右移缩小窗口 # 此处可根据题意维护/更新答案如记录最大/最小窗口等 # 右指针右移扩大窗口 right 1例题3. 无重复字符的最长子串 - 力扣LeetCode给定一个字符串s请你找出其中不含有重复字符的最长 子串的长度。示例 1:输入:s abcabcbb输出:3解释:因为无重复字符的最长子串是abc所以其长度为 3。注意 bca 和 cab 也是正确答案。public class Solution { public int LengthOfLongestSubstring(string s) { int left0; int right 0; int ans 0; Dictionarychar,int dic new Dictionarychar,int(); while(rights.Length) { while(dic.ContainsKey(s[right])) { dic.Remove(s[left]); left; } dic.Add(s[right],1); ans Math.Max(ans,right-left1); right; } return ans; } }