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

Javajava算法

Java 滑动窗口算法实战：LeetCode 经典题目解析

滑动窗口算法是解决区间类问题的高效手段，核心在于利用同向双指针维护动态窗口。结合 Java 语言，通过最小长度子数组、无重复字符最长子串、水果成篮等八个 LeetCode 经典案例，演示如何从暴力解法优化至 O(N) 复杂度。内容涵盖哈希表辅助去重、正难则反转换思路、固定窗口与可变窗口切换等关键技巧，旨在帮助开发者快速掌握此类算法题的通用模式与实战要点。

1qazxsw2发布于 2026/3/23更新于 2026/4/251 浏览

Java 滑动窗口算法实战：LeetCode 经典题目解析

滑动窗口算法核心思路

滑动窗口（Sliding Window）是处理数组或字符串区间问题的利器，本质上是同向双指针的一种优化应用。相比暴力解法的双重循环，它通过维护一个动态窗口，避免了重复计算，将时间复杂度从 O(N^2) 降到了 O(N)。在实际解题中，我们通常使用 left 和 right 两个指针，它们都向右移动且不回退，根据题目条件决定何时收缩左边界或扩展右边界。

下面结合几个经典的 LeetCode 题目，看看如何在 Java 中落地这一思想。

长度最小的子数组

题目描述 给定一个包含正整数的数组和一个目标值 target，找出满足其和 ≥ target 的连续子数组的最小长度。如果不存在，返回 0。

解题思路 暴力解法需要双重循环遍历所有可能的区间，效率较低。观察发现，当窗口内元素和已经大于等于 target 时，继续扩大右边界只会让长度变长，不符合'最小'的要求。此时应该尝试收缩左边界，直到和小于 target 为止。

具体做法是使用 sum 记录当前窗口和，right 负责入窗口，left 负责出窗口。当 sum >= target 时更新最小长度，并不断移除 left 指向的元素。

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++]; // 出窗口
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

时间复杂度：O(N)，空间复杂度：O(1)

无重复字符的最长子串

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) {
                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]; // 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);
    }
}