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

Javajava算法

Java 滑动窗口算法经典题目解析

综述由AI生成Java 滑动窗口算法针对多个 LeetCode 题目提供了解题思路，涵盖长度最小子数组、无重复字符最长子串、最大连续 1 的个数等问题。核心思想是利用同向双指针维护动态窗口，替代暴力枚举，将时间复杂度优化至 O(N)。文中包含具体代码实现及复杂度分析，展示了哈希表结合滑动窗口的常见模式。

链路追踪发布于 2026/3/16更新于 2026/4/252 浏览

Java 滑动窗口算法经典题目解析

滑动窗口算法

滑动窗口是一种常用的双指针技巧，通过维护一个动态区间来解决子数组或子串问题。相比暴力解法，它能有效降低时间复杂度。

长度最小的子数组

图示说明

题目解析：给定一个正整数数组和一个目标值，寻找和大于等于目标值的最短连续子数组长度，不存在则返回 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;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] hash = new int[128]; // 使用数组模拟哈希表，ASCII 码值作为下标
        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) { // 0 的个数超过 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) { // 种类超过 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]; // p 的字符信息
        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);
    }
}