滑动窗口是一种经典的算法技巧,就像在处理一系列动态数据时,用一扇可以滑动的“窗口”来捕捉一段连续的子数组或子字符串。通过不断地移动窗口的起点或终点,我们能够以较低的时间复杂度来解决一系列问题。在这篇文章中,我们将通过几个经典的 LeetCode 题目,使用 Java 语言来详细讲解滑动窗口的应用。
题目背景:
朋友小明在编程比赛中遇到了一个问题:如何在一个长字符串中找到所有与目标字符串异位的子串?我们需要通过滑动窗口找到所有这些位置。
题目描述:
给定两个字符串 s 和 p,找出 s 中所有 p 的异位词的起始索引。字符串仅包含小写字母,并且 p 和 s 的长度都不超过 20,000。
示例:
- 输入: s = "cbaebabacd", p = "abc"
- 输出: [0, 6]
-
代码实现:
- import java.util.*;
-
- public class Solution {
- public List<Integer> findAnagrams(String s, String p) {
- List<Integer> result = new ArrayList<>();
- if (s.length() < p.length()) return result;
-
- int[] pCount = new int[26]; // 记录字符串 p 中字符的频率
- int[] sCount = new int[26]; // 记录当前窗口中字符的频率
-
- for (char c : p.toCharArray()) {
- pCount[c - 'a']++;
- }
-
- int left = 0;
- for (int right = 0; right < s.length(); right++) {
- sCount[s.charAt(right) - 'a']++;
-
- // 如果窗口大小大于 p 的长度,收缩窗口
- if (right - left + 1 > p.length()) {
- sCount[s.charAt(left) - 'a']--;
- left++;
- }
-
- // 判断窗口内的字符频率与 p 是否一致
- if (Arrays.equals(sCount, pCount)) {
- result.add(left);
- }
- }
-
- return result;
- }
- }
-
分析:
题目背景:
我们去果园摘水果,朋友们想知道,如何在一个果树排列中,找到最长的连续子集,使得我们可以只用两个篮子装下这些水果。
题目描述:
在一排树中,第 i 棵树上有 tree[i] 型号的水果。你可以选择两个篮子,每个篮子只能装一种型号的水果。你需要找到可以采摘的水果的最大数量。
示例:
- 输入: tree = [1,2,1,2,1,3,3,4,3]
- 输出: 4
-
代码实现:
- import java.util.*;
-
- public class Solution {
- public int totalFruit(int[] tree) {
- Map<Integer, Integer> basket = new HashMap<>();
- int left = 0, maxFruit = 0;
-
- for (int right = 0; right < tree.length; right++) {
- basket.put(tree[right], basket.getOrDefault(tree[right], 0) + 1);
-
- // 如果篮子里有超过两种水果,开始收缩窗口
- while (basket.size() > 2) {
- basket.put(tree[left], basket.get(tree[left]) - 1);
- if (basket.get(tree[left]) == 0) {
- basket.remove(tree[left]);
- }
- left++;
- }
-
- // 记录当前窗口的最大长度
- maxFruit = Math.max(maxFruit, right - left + 1);
- }
-
- return maxFruit;
- }
- }
-
分析:
题目背景:
小丽正在玩一个文字游戏,要求她通过最多 k 次字符替换,将字符串中的一段字符变成相同的字符。她希望找出其中能够获得最长重复字符子串的长度。
题目描述:
给你一个仅由大写英文字母组成的字符串 s,你可以最多将 k 个字符替换为任意字符,求在执行上述操作后,能够得到的最长重复字符的子串的长度。
示例:
- 输入: s = "AABABBA", k = 1
- 输出: 4
-
代码实现:
- public class Solution {
- public int characterReplacement(String s, int k) {
- int[] count = new int[26]; // 记录窗口内字符的频率
- int maxCount = 0, maxLen = 0, left = 0;
-
- for (int right = 0; right < s.length(); right++) {
- count[s.charAt(right) - 'A']++;
- maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
-
- // 如果当前窗口大小减去窗口中最多的字符数大于 k,收缩窗口
- if (right - left + 1 - maxCount > k) {
- count[s.charAt(left) - 'A']--;
- left++;
- }
-
- maxLen = Math.max(maxLen, right - left + 1);
- }
-
- return maxLen;
- }
- }
-
分析:
滑动窗口在处理连续子数组或子字符串问题时展现了极大的灵活性。通过维护一个动态窗口,滑动窗口不仅能够帮助我们有效解决问题,还可以极大地优化时间复杂度。在这些例子中,我们用 Java 语言展示了滑动窗口在寻找异位词、最大水果采摘量、以及字符替换中的应用。滑动窗口算法的威力在于,它不仅高效,而且能够适应各种复杂的题目。