当前位置：首页 > news >正文

滑动窗口

news 2025/9/14 17:32:24

模板

本质上是双指针（快慢指针）的一种应用，可以理解为用两个指针维护一个区间，动态调整区间范围以满足题目要求。

常用于查找满足某些条件的连续子区间。

固定长度滑动窗口

left = 0  # 窗口左边界
right = 0  # 窗口右边界while right < len(nums):# 将当前元素加入窗口window.append(nums[right])# 判断当前窗口长度是否达到 window_sizeif right - left + 1 >= window_size:# 在窗口长度达到要求时，进行答案的统计或更新# ... 这里根据题目需求维护/更新答案# 移除窗口最左侧元素，窗口向右滑动window.popleft()left += 1  # 左指针右移，缩小窗口长度，保持窗口长度为 window_size# 右指针右移，扩大窗口right += 1

不定长度滑动窗口

# 初始化左右指针，均指向数组起始位置
left = 0
right = 0# 主循环，右指针遍历整个数组
while right < len(nums):# 将当前右指针指向的元素加入窗口window.append(nums[right])# 当窗口不满足题目要求时，缩小窗口（移动左指针）while 窗口需要缩小:# 此处可根据题意维护/更新答案window.popleft()  # 移除左边界元素left += 1         # 左指针右移，缩小窗口# 此处可根据题意维护/更新答案（如记录最大/最小窗口等）# 右指针右移，扩大窗口right += 1

题目

1、拆分子串，长度限定在[min, max]

思路：双指针

import java.util.ArrayList;
import java.util.List;public class Main {public static void main(String[] args) {String str = "abcdefghijk";System.out.println(new Main().getAllSub(str, 6, 12));System.out.println(new Main().getAllSub_1(str, 6, 12));}List<String> getAllSub_1(String str, int min, int max) {List<String> res = new ArrayList<>();int n = str.length();for (int i = 0; i < n; i++) {for (int j = i; j < Math.min(n, i + max); j++) {int len = j - i + 1;if (len >= min && len <= max) {res.add(str.substring(i, j + 1));}}}return res;}List<String> getAllSub(String str, int min, int max) {List<String> res = new ArrayList<>();int n = str.length();int left = 0;while (left < n) {int right = left;while (right < n) {int len = right - left + 1;if (len >= min && len <= max) {res.add(str.substring(left, right + 1));} else if (len > max) {break;}right++;}left++;}return res;}
}

2、1343. 大小为 K 且平均值大于等于阈值的子数组数目

给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

leetcode-1343

class Solution {public int numOfSubarrays(int[] arr, int k, int threshold) {int left=0,right=0,window_size=0;int res = 0;while (right < arr.length) {window_size += arr[right];if (right-left+1 >= k) {if (window_size >= k*threshold) {res++;}window_size -= arr[left];left++;}right++;}return res;}
}

3、无重复字符的最长子串

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

子字符串：是字符串中连续的、非空的字符序列。

leetcode-3

class Solution {public int lengthOfLongestSubstring(String s) {int left=0,right=0;int res = 0;Map<Character,Integer> map=new HashMap<>();while (right<s.length()) {char c = s.charAt(right);right++;map.put(c, map.getOrDefault(c, 0)+1);while (map.get(c) > 1) {char temp = s.charAt(left);map.put(temp, map.get(temp)-1);left++;}res = Math.max(res, right - left);}return res;}
}