深入理解 Java 中的滑动窗口算法

简介

滑动窗口算法是一种在数组或字符串上进行高效处理的技术。它通过维护一个动态的窗口，在遍历数据的过程中不断调整窗口的范围，从而以线性时间复杂度解决许多复杂的问题，如查找最长子串、计算子数组的最大和等。在 Java 中，滑动窗口算法具有广泛的应用场景，掌握这一技术对于提升算法能力和解决实际问题非常有帮助。

滑动窗口基础概念

滑动窗口可以想象成在一个数组或字符串上移动的“窗口”。这个窗口有左右两个边界，通过移动边界来调整窗口的大小和位置。在处理数据时，窗口会根据具体问题的需求，在数据序列上逐步滑动，同时对窗口内的数据进行特定的计算或操作。

例如，在一个整数数组 [1, 3, 5, 7, 9] 中，如果我们设置窗口大小为 3，最初窗口覆盖的元素是 [1, 3, 5]，然后窗口向右滑动一个位置，覆盖 [3, 5, 7]，再滑动则覆盖 [5, 7, 9]。

滑动窗口在 Java 中的使用方法

在 Java 中实现滑动窗口算法，通常需要使用两个指针来表示窗口的左右边界，这两个指针被称为左指针（left）和右指针（right）。以下是一个简单的框架代码示例：

public class SlidingWindowExample {
    public static int slidingWindow(int[] nums, int target) {
        int left = 0, right = 0;
        int sum = 0;
        int result = 0;

        while (right < nums.length) {
            sum += nums[right];
            right++;

            while (sum >= target) {
                // 在这里对满足条件的窗口进行处理
                result = Math.max(result, right - left);
                sum -= nums[left];
                left++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 9};
        int target = 11;
        int result = slidingWindow(nums, target);
        System.out.println("满足条件的最大窗口大小: " + result);
    }
}

在这段代码中： 1. 初始化左指针 left 和右指针 right 都指向数组的起始位置。 2. 使用 while 循环移动右指针，扩大窗口，同时累加窗口内元素的和。 3. 当窗口内元素的和满足条件（sum >= target）时，进入内层 while 循环，通过移动左指针缩小窗口，并更新结果。

常见实践

1. 无重复字符的最长子串

题目描述：给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

public class LongestSubstringWithoutRepeatingChars {
    public static int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;
        int maxLength = 0;
        boolean[] charSet = new boolean[128];

        while (right < s.length()) {
            char c = s.charAt(right);
            if (charSet[c]) {
                while (s.charAt(left) != c) {
                    charSet[s.charAt(left)] = false;
                    left++;
                }
                left++;
            } else {
                charSet[c] = true;
                maxLength = Math.max(maxLength, right - left + 1);
            }
            right++;
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        int result = lengthOfLongestSubstring(s);
        System.out.println("无重复字符的最长子串长度: " + result);
    }
}

2. 和大于等于目标值的最小子数组长度

题目描述：给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。

public class MinimumSizeSubarraySum {
    public static int minSubArrayLen(int s, int[] nums) {
        int left = 0, right = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

        while (right < nums.length) {
            sum += nums[right];
            right++;

            while (sum >= s) {
                minLength = Math.min(minLength, right - left);
                sum -= nums[left];
                left++;
            }
        }
        return minLength == Integer.MAX_VALUE? 0 : minLength;
    }

    public static void main(String[] args) {
        int s = 7;
        int[] nums = {2, 3, 1, 2, 4, 3};
        int result = minSubArrayLen(s, nums);
        System.out.println("和大于等于目标值的最小子数组长度: " + result);
    }
}

最佳实践

明确窗口维护的状态：在开始编写代码前，清楚地确定窗口需要维护的状态，例如元素的和、是否有重复元素等。这有助于准确地编写窗口的扩展和收缩逻辑。
避免不必要的计算：在窗口滑动过程中，尽量复用之前的计算结果。例如，当窗口滑动一个位置时，如果可以通过简单的加减法更新窗口的状态，就避免重新计算整个窗口的值。
边界条件处理：仔细考虑边界条件，如数组或字符串为空、窗口大小超过数据范围等情况。确保代码在各种情况下都能正确运行。

小结

滑动窗口算法是 Java 编程中一种强大且高效的技术，通过灵活运用左右指针来维护动态窗口，可以解决许多涉及数组和字符串处理的问题。掌握滑动窗口的基础概念、使用方法、常见实践以及最佳实践，能够提升我们解决复杂算法问题的能力，提高代码的效率和可读性。

参考资料

《算法导论》
LeetCode 官方文档及相关题解
各大技术论坛和博客上关于滑动窗口算法的讨论和文章