Java案例如何实现滑动窗口？

Java滑动窗口实现详解

滑动窗口是一种常用的算法技巧,主要解决连续子数组/子字符串问题，以下是几种常见实现方式：

固定长度滑动窗口

public class FixedSlidingWindow {
    // 示例：计算长度为k的子数组最大和
    public static int maxSumWindow(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return 0;
        }
        // 计算第一个窗口的和
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        int maxSum = windowSum;
        // 滑动窗口
        for (int i = k; i < nums.length; i++) {
            windowSum += nums[i] - nums[i - k];  // 加入新元素，移除旧元素
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] nums = {1, 4, 2, 10, 23, 3, 1, 0, 20};
        int k = 4;
        System.out.println("最大和为: " + maxSumWindow(nums, k));  // 输出: 39
    }
}

可变长度滑动窗口

public class VariableSlidingWindow {
    // 示例：找出和大于等于target的最短子数组长度
    public static int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];  // 扩展窗口
            // 收缩窗口
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println("最短子数组长度: " + minSubArrayLen(target, nums));  // 输出: 2
    }
}

字符串滑动窗口通用模板

public class StringSlidingWindow {
    // 通用模板：查找最长无重复字符子串
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int left = 0;
        int maxLen = 0;
        Map<Character, Integer> charMap = new HashMap<>();
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 如果字符已出现，移动左边界
            if (charMap.containsKey(c) && charMap.get(c) >= left) {
                left = charMap.get(c) + 1;
            }
            // 更新字符位置
            charMap.put(c, right);
            // 计算当前窗口长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("最长无重复子串长度: " + lengthOfLongestSubstring(s));  // 输出: 3
    }
}

通用滑动窗口框架

public class SlidingWindowFramework {
    // 滑动窗口通用模板
    public static List<Integer> slidingWindowTemplate(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        int left = 0, right = 0;
        // 维护窗口状态的变量
        int windowSum = 0;
        int maxSum = Integer.MIN_VALUE;
        while (right < nums.length) {
            // 1. 扩展窗口：加入右边元素
            int num = nums[right];
            windowSum += num;
            // 2. 根据条件收缩窗口
            // 窗口长度固定为k
            while (right - left + 1 > 3) {  // 假设窗口最大长度为3
                windowSum -= nums[left];
                left++;
            }
            // 3. 更新结果
            if (right - left + 1 == 3) {
                maxSum = Math.max(maxSum, windowSum);
            }
            // 4. 继续移动右指针
            right++;
        }
        result.add(maxSum);
        return result;
    }
}

实际应用示例：最小覆盖子串

public class MinWindowSubstring {
    // 找出包含目标字符串所有字符的最小子串
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        // 初始化需要字符的计数
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;  // 满足条件的字符数
        int start = 0;  // 记录最小子串起始位置
        int len = Integer.MAX_VALUE;  // 记录最小子串长度
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 更新窗口内数据
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断是否要收缩窗口
            while (valid == need.size()) {
                // 更新最小子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                char d = s.charAt(left);
                left++;
                // 更新窗口内数据
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println("最小覆盖子串: " + minWindow(s, t));  // 输出: "BANC"
    }
}

1. 固定窗口：left和right同步移动，每次加入新元素并删除旧元素
2. 可变窗口：right不断右移，当条件满足时左移left
3. 关键变量：
   • left/right：窗口边界
   • window：窗口内数据状态
   • valid：满足条件的计数
   • result：记录最终结果

选择哪种实现取决于具体需求：固定长度问题用第一种，可变长度用第二种，字符串匹配用第三种。