Java 滑动窗口算法经典题目练习 | 极客日志

Javajava算法

Java 滑动窗口算法经典题目练习

本文通过多个 LeetCode 经典例题，详细讲解了 Java 语言中滑动窗口算法的应用。涵盖长度最小子数组、无重复字符最长子串、最大连续 1 的个数等题目，提供暴力解法对比及优化后的双指针实现代码，分析时间与空间复杂度，帮助读者掌握该算法的核心逻辑与实战技巧。

BigDataPan发布于 2026/3/30更新于 2026/4/131 浏览

长度最小的子数组

在这里插入图片描述

题目解析：给定一个正整数数组和一个目标值，找出和大于等于目标值的连续区间的最小长度。如果不存在则返回 0。 算法原理：

暴力解法：双重 for 循环遍历所有情况，当满足条件时更新结果。由于是正整数数组，一旦区间和超过目标值，继续扩大区间只会增加长度，因此可以优化。

滑动窗口（同向双指针）：使用 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;
           nums.length;
         (   , right = ; right < n; right++) {
            sum += nums[right]; 
             (sum >= target) {
                len = Math.min(len, right - left + ); 
                sum -= nums[left++]; 
            }
        }
         len == Integer.MAX_VALUE ?  : len;
    }
}

相关免费在线工具

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
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] hash = new int[128]; // 使用数组表示 hash
        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;
    }
}

class Solution {
    public int longestOnes(int[] nums, int k) {
        int len = 0;
        int n = nums.length;
        int count = 0; // 统计当前区间 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;
    }
}

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;
    }
}

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;
    }
}

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;
    }
}

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);
    }
}

Java 滑动窗口算法经典题目练习

长度最小的子数组

更多推荐文章

相关免费在线工具

无重复字符的最长子串

最大连续 1 的个数 III

将 x 减到 0 的最小操作数

水果成蓝

找到字符串中所有字母异位词

串联所有单词的子串

最小覆盖子串

Java 滑动窗口算法经典题目练习

长度最小的子数组

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

无重复字符的最长子串

最大连续 1 的个数 III

将 x 减到 0 的最小操作数

水果成蓝

找到字符串中所有字母异位词

串联所有单词的子串

最小覆盖子串