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

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

无重复字符的最长子串

题目解析：找出字符串 s 中最长连续不重复子串的长度。

算法原理：

1. 滑动窗口 + 哈希表：使用 left 和 right 指针。right 遍历字符串并记录字符出现次数。若字符重复（计数 > 1），则移动 left 直到去重。

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

最大连续 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; // 统计当前区间 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;
    }
}

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

将 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) { // 种类超过 2，出窗口
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0) {
                    kinds--;
                }
                left++;
            }
            len = Math.max(len, right - left + 1);
        }
        return len;
    }
}

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

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

题目解析：在 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]; // 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;
    }
}

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

串联所有单词的子串

题目解析：在 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)