Java滑动窗口算法题目练习
原创
滑动窗口算法是处理数组/字符串中子序列问题的高效方法，尤其适合解决“连续子元素”相关问题（如子数组、子串）。以下是几道经典的Java滑动窗口算法练习题，附带解题思路和代码实现，供你练习参考：
1. 无重复字符的最长子串（LeetCode 3）
题目：给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
示例：
输入: s = "abcabcbb" → 输出: 3（解释: 因为无重复字符的最长子串是 "abc"）
思路：
- 用 哈希集合 记录窗口内的字符，避免重复。
- 左指针
left 和右指针 right 维护当前窗口 [left, right]。 - 右指针右移，若字符重复，则左指针右移并移除集合中对应字符，直到无重复。
- 每次移动右指针时，更新最大长度。
代码：
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// 若字符重复，移动左指针直到无重复
while (set.contains(c)) {
set.remove(s.charAt(left));
left++;
}
set.add(c);
// 更新最大长度
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}2. 长度最小的子数组（LeetCode 209）
题目：给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的 连续子数组，并返回其长度。若不存在，返回 0。
示例：
输入: target = 7, nums = [2,3,1,2,4,3] → 输出: 2（解释: 子数组 [4,3] 的和为7）
思路：
- 用 滑动窗口求和，右指针扩展窗口，左指针收缩窗口以寻找最小长度。
- 当窗口和
≥ target 时，尝试左移左指针，缩小窗口并更新最小长度。
代码：
public int minSubArrayLen(int target, int[] nums) {
int minLen = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
// 当和满足条件时，收缩左指针
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}3. 滑动窗口最大值（LeetCode 239）
题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
示例：
输入: nums = [1,3,-1,-3,5,3,6,7], k = 3 → 输出: [3,3,5,5,6,7]
思路：
- 用 双端队列（Deque） 存储窗口内元素的 索引，保持队列中元素对应的数值 单调递减。
- 右指针移动时，移除队列中所有小于当前元素的索引（它们不可能是最大值），再加入当前索引。
- 左指针移动时，若队首索引超出窗口范围，移除队首。
- 每次右指针移动到窗口末尾时，队首即为当前窗口的最大值。
代码：
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) return new int[0];
int[] res = new int[nums.length - k + 1];
Deque<Integer> deque = new LinkedList<>(); // 存储索引，保持数值递减
int index = 0;
for (int right = 0; right < nums.length; right++) {
// 移除队列中小于当前元素的索引（它们不可能是最大值）
while (!deque.isEmpty() && nums[right] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(right);
// 移除窗口外的索引（左边界为 right - k + 1）
if (deque.peekFirst() <= right - k) {
deque.pollFirst();
}
// 当窗口大小达到 k 时，记录最大值（队首）
if (right >= k - 1) {
res[index++] = nums[deque.peekFirst()];
}
}
return res;
}4. 找到字符串中所有字母异位词（LeetCode 438）
题目：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。异位词指由相同字母重排列形成的字符串（包括相同的字符串）。
示例：
输入: s = "cbaebabacd", p = "abc" → 输出: [0,6]（解释: 子串 s[0..2]="cba" 和 s[6..8]="bac" 是 p 的异位词）
思路：
- 用 哈希表（或数组） 记录
p 中字符的频率，再用滑动窗口匹配 s 中对应长度的子串频率。 - 窗口大小固定为
p 的长度，右指针移动时更新窗口内字符频率，左指针同步移动以保持窗口大小。 - 若窗口内频率与
p 完全匹配，则记录左指针索引。
代码：
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) return res;
int[] pCount = new int[26]; // 记录p中字符频率
int[] sCount = new int[26]; // 记录窗口中字符频率
// 初始化p的频率和s的初始窗口频率
for (int i = 0; i < pLen; i++) {
pCount[p.charAt(i) - 'a']++;
sCount[s.charAt(i) - 'a']++;
}
// 检查初始窗口是否匹配
if (Arrays.equals(pCount, sCount)) {
res.add(0);
}
// 滑动窗口（右指针从pLen开始）
for (int right = pLen; right < sLen; right++) {
// 加入右字符，移除左字符（保持窗口大小为pLen）
sCount[s.charAt(right) - 'a']++;
sCount[s.charAt(right - pLen) - 'a']--;
// 若频率匹配，记录左指针（right - pLen + 1）
if (Arrays.equals(pCount, sCount)) {
res.add(right - pLen + 1);
}
}
return res;
}总结
滑动窗口算法的核心是通过 双指针（左右指针） 维护一个动态窗口，根据问题条件扩展或收缩窗口，从而在 O(n) 时间复杂度内解决问题（避免暴力法的O(n²)）。练习时需注意：
- 窗口是“连续的”，适用于子数组/子串问题。
- 区分“固定窗口大小”（如第4题）和“可变窗口大小”（如第1、2题）的处理逻辑。
- 合理使用辅助数据结构（哈希表、队列）优化窗口内元素的查询/更新效率。
可以尝试在LeetCode上提交这些代码，进一步熟悉滑动窗口的应用场景和细节处理~
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
