跳到主要内容Java 滑动窗口算法经典题目解析 | 极客日志Javajava算法
Java 滑动窗口算法经典题目解析
Java 滑动窗口算法针对多个 LeetCode 题目提供了解题思路,涵盖长度最小子数组、无重复字符最长子串、最大连续 1 的个数等问题。核心思想是利用同向双指针维护动态窗口,替代暴力枚举,将时间复杂度优化至 O(N)。文中包含具体代码实现及复杂度分析,展示了哈希表结合滑动窗口的常见模式。
链路追踪103 浏览 滑动窗口算法
滑动窗口是一种常用的双指针技巧,通过维护一个动态区间来解决子数组或子串问题。相比暴力解法,它能有效降低时间复杂度。
长度最小的子数组

题目解析:给定一个正整数数组和一个目标值,寻找和大于等于目标值的最短连续子数组长度,不存在则返回 0。
算法原理:
- 暴力解法:双重循环遍历所有情况,效率低。
- 滑动窗口:使用 left 和 right 两个同向指针。right 向右扩展窗口累加 sum,当 sum >= target 时更新最小长度,然后移动 left 缩小窗口直到 sum < target。

class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int len = Integer.MAX_VALUE;
int n = nums.length;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right];
while (sum >= target) {
len = Math.min(len, right - left + 1);
sum -= nums[left++];
}
}
len == Integer.MAX_VALUE ? : len;
}
}
return
0
无重复字符的最长子串
题目解析:找出字符串 s 中最长连续不重复子串的长度。
- 滑动窗口 + 哈希表:使用 left 和 right 指针。right 遍历字符串并记录字符出现次数。若字符重复(计数 > 1),则移动 left 直到去重。
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] hash = new int[128];
int len = 0;
char[] chars = s.toCharArray();
for (int left = 0, right = 0; right < chars.length; right++) {
hash[chars[right]]++;
while (hash[chars[right]] > 1) {
hash[chars[left++]]--;
}
len = Math.max(len, right - left + 1);
}
return len;
}
}
最大连续 1 的个数 III
题目解析:找到最大连续 1 的个数,最多可以反转 k 个 0。
算法原理:将问题转换为找出一个最长子数组,其中 0 的个数不超过 k 个。
class Solution {
public int longestOnes(int[] nums, int k) {
int len = 0;
int n = nums.length;
int count = 0;
for (int left = 0, right = 0; right < n; right++) {
if (nums[right] == 0) {
count++;
}
while (count > k) {
if (nums[left++] == 0) {
count--;
}
}
len = Math.max(len, right - left + 1);
}
return len;
}
}
将 x 减到 0 的最小操作数
题目解析:每次从数组最左或最右取数减去 x,求最小操作数。
算法原理:正难则反,转换为在数组中找最长的连续子数组,使其和为 总和 - x。
class Solution {
public int minOperations(int[] nums, int x) {
int sum = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
int target = sum - x;
if (target < 0) {
return -1;
}
int total = 0;
int len = -1;
for (int left = 0, right = 0; right < n; right++) {
total += nums[right];
while (total > target) {
total -= nums[left++];
}
if (total == target) {
len = Math.max(len, right - left + 1);
}
}
return len == -1 ? -1 : n - len;
}
}
水果成篮
题目解析:用两个篮子放水果,每个篮子只能放一种,不能跳过,求最多摘多少水果。
算法原理:转换为找出最长子数组,且里面不超过两种水果。
class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length;
int[] hash = new int[n + 1];
int len = 0;
int kinds = 0;
for (int left = 0, right = 0; right < n; right++) {
if (hash[fruits[right]] == 0) {
kinds++;
}
hash[fruits[right]]++;
while (kinds > 2) {
hash[fruits[left]]--;
if (hash[fruits[left]] == 0) {
kinds--;
}
left++;
}
len = Math.max(len, right - left + 1);
}
return len;
}
}
找到字符串中所有字母异位词
题目解析:在 s 中找到所有 p 的异位词子串的起始索引。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ret = new ArrayList<>();
char[] sc = s.toCharArray();
char[] pc = p.toCharArray();
int[] hash1 = new int[26];
for (char ch : pc) {
hash1[ch - 'a']++;
}
int[] hash2 = new int[26];
int n = p.length();
int count = 0;
for (int left = 0, right = 0; right < s.length(); right++) {
char in = sc[right];
if (++hash2[in - 'a'] <= hash1[in - 'a']) {
count++;
}
if (right - left + 1 > n) {
char out = sc[left++];
if (hash2[out - 'a']-- <= hash1[out - 'a']) {
count--;
}
}
if (count == n) {
ret.add(left);
}
}
return ret;
}
}
串联所有单词的子串
题目解析:在 s 中找出包含 words 中所有单词的子串起始位置。
算法原理:与字母异位词类似,但需将单词视为整体处理。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ret = new ArrayList<>();
Map<String, Integer> hash1 = new HashMap<>();
for (String word : words) {
hash1.put(word, hash1.getOrDefault(word, 0) + 1);
}
int n = words[0].length();
int m = words.length;
for (int i = 0; i < n; i++) {
Map<String, Integer> hash2 = new HashMap<>();
for (int left = i, right = i, count = 0; right <= s.length() - n; right += n) {
String in = s.substring(right, right + n);
hash2.put(in, hash2.getOrDefault(in, 0) + 1);
if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
count++;
}
if (right - left + 1 > m * n) {
String out = s.substring(left, left + n);
if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
count--;
}
hash2.put(out, hash2.get(out) - 1);
if (hash2.get(out) == 0) {
hash2.remove(out);
}
left += n;
}
if (count == m) {
ret.add(left);
}
}
}
return ret;
}
}
时间复杂度:O(m * n),空间复杂度:O(n)
最小覆盖子串
题目解析:在 s 中找到包含 t 中所有字符的最小子串。
算法原理:滑动窗口 + 哈希表,动态调整窗口大小以满足条件。
class Solution {
public String minWindow(String s, String t) {
char[] sc = s.toCharArray();
char[] tc = t.toCharArray();
int[] hash1 = new int[128];
int kinds = 0;
for (char ch : tc) {
if (hash1[ch]++ == 0) {
kinds++;
}
}
int minlen = Integer.MAX_VALUE;
int begin = -1;
int[] hash2 = new int[128];
for (int left = 0, right = 0, count = 0; right < s.length(); right++) {
char in = sc[right];
if (++hash2[in] == hash1[in]) {
count++;
}
while (kinds == count) {
if (right - left + 1 < minlen) {
begin = left;
minlen = right - left + 1;
}
char out = sc[left++];
if (hash2[out]-- == hash1[out]) {
count--;
}
}
}
return begin == -1 ? "" : s.substring(begin, begin + minlen);
}
}
时间复杂度:O(m + n),空间复杂度:O(1)
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online