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

滑动窗口算法

news 2024/11/6 17:49:33

这是一篇关于滑动窗口的教程，涵盖固定窗口和可变窗口的基本概念、应用场景，并通过实际的 Java 示例代码帮助理解。

滑动窗口算法教程

滑动窗口（Sliding Window）是一种非常高效的算法技巧，常用于处理序列（如数组、字符串等）中的问题，特别是与子数组或子字符串相关的问题。通过维护一个窗口（通常是一个连续的元素范围），并在序列上滑动，滑动窗口技巧能够大大减少计算量，提升程序性能。

1. 滑动窗口概述

滑动窗口的核心思想是使用两个指针（通常称为左指针和右指针）来表示当前窗口的范围。右指针负责扩展窗口，左指针负责收缩窗口，以满足题目要求的条件。通过左右指针的移动，窗口会在数据上滑动，从而高效地求解问题。

窗口的两种类型：

固定窗口大小：窗口的大小是固定的，每次滑动时，窗口的范围不变，只是向右或向左移动。
可变窗口大小：窗口的大小可以变化，通常根据某些条件来扩展或收缩窗口。

2. 固定窗口大小

固定窗口大小的滑动窗口指的是窗口的大小在整个过程中保持不变。每次滑动时，窗口只向前推进，新的元素进入窗口时，最旧的元素会被移除。

应用场景：

常用于求解固定大小的子数组或子字符串的相关问题，例如计算某个固定窗口大小的子数组的和、平均值、最大值等。

示例问题：

问题：给定一个数组，求所有大小为 k 的子数组的和。

public class FixedSizeSlidingWindow {public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6};int k = 3;int result = maxSum(arr, k);System.out.println("Maximum sum of any subarray of size " + k + " is: " + result);}public static int maxSum(int[] arr, int k) {// 初始化窗口的总和int windowSum = 0;int maxSum = 0;// 第一步：计算窗口初始值for (int i = 0; i < k; i++) {windowSum += arr[i];}maxSum = windowSum;// 第二步：滑动窗口for (int i = k; i < arr.length; i++) {// 滑动窗口：减去左边的元素，加上右边的元素windowSum += arr[i] - arr[i - k];maxSum = Math.max(maxSum, windowSum);}return maxSum;}
}

解释：

初始时，我们计算数组前 k 个元素的和。
然后，通过滑动窗口，逐步向右滑动，每次移出窗口左侧的元素，并加入新的右侧元素。
在每次滑动时，更新窗口的和，并记录最大值。

3. 可变窗口大小

可变窗口大小的滑动窗口指的是窗口的大小是动态变化的，通常依据某些条件来扩展或收缩窗口。这种方法通常用于一些更复杂的情况，如寻找某种满足条件的子数组。

应用场景：

常用于解决一些求解最大、最小子数组的问题，如：

寻找一个和小于某个值的最长子数组。
寻找一个包含所有不同字符的最小子字符串。

示例问题：

问题：给定一个字符串，找出其中没有重复字符的最长子字符串的长度。

import java.util.HashSet;public class VariableSizeSlidingWindow {public static void main(String[] args) {String input = "abcabcbb";System.out.println("Length of the longest substring without repeating characters: " + lengthOfLongestSubstring(input));}public static int lengthOfLongestSubstring(String s) {HashSet<Character> set = new HashSet<>();int left = 0; // 左指针int maxLength = 0;// 右指针从左到右滑动for (int right = 0; right < s.length(); right++) {// 如果字符已经存在于集合中，收缩窗口，移动左指针while (set.contains(s.charAt(right))) {set.remove(s.charAt(left));left++;}// 将当前字符加入集合set.add(s.charAt(right));// 更新最大长度maxLength = Math.max(maxLength, right - left + 1);}return maxLength;}
}