Java 滑动窗口实战：如何用双指针解决「最长重复子数组」问题

在算法问题中，子数组相关挑战常涉及连续序列的处理。本文将聚焦于「最长重复子数组」问题：给定两个整数数组 $A$ 和 $B$，找到它们的最长公共连续子数组的长度。子数组必须是连续的，例如 $A = [1,2,3,2,1]$ 和 $B = [3,2,1,4,7]$ 中，最长公共子数组是 $[3,2,1]$，长度为 3。我们将使用 Java 实现滑动窗口技术结合双指针来解决此问题，确保代码简洁且易于理解。

问题理解

「最长重复子数组」要求找出两个数组中长度最大的公共连续部分。输入为两个数组 $A$ 和 $B$，输出为整数表示最大长度。例如：

• $A = [0,1,2,3,4]$，$B = [2,3,4,5]$，输出为 3（子数组 $[2,3,4]$）。
• $A = [1,0,0,0,1]$，$B = [1,0,0,1,1]$，输出为 3（子数组 $[0,0,0]$ 或 $[0,0,1]$）。

关键点在于子数组的连续性，这使滑动窗口成为理想选择。滑动窗口技术通过动态调整窗口边界来遍历数组，而双指针（通常指起始指针和结束指针）用于控制窗口大小。这里，我们将使用双指针模拟窗口的移动，比较数组元素。

解法思路：滑动窗口与双指针

为了解决此问题，我们采用以下步骤：

1. 核心思想：遍历所有可能的对齐点。由于两个数组可能起始位置不同，我们考虑 $A$ 和 $B$ 的相对偏移。对于每个偏移量，使用双指针（$i$ 和 $j$）定义窗口，比较元素是否相等。
2. 滑动窗口流程：
   • 外层循环：遍历偏移量 $d$，范围从 $-(B.\text{length} - 1)$ 到 $A.\text{length} - 1$。这覆盖了所有可能对齐（例如 $d=0$ 表示 $A$ 和 $B$ 从相同索引开始）。
   • 内层处理：对于每个 $d$，使用指针 $k$ 从 0 开始，比较 $A[i + k]$ 和 $B[j + k]$（需处理边界）。如果元素相等，增加当前匹配长度；否则重置长度。
   • 记录最大值：在每次比较中，更新最大长度。
3. 优势：该方法避免了不必要的重复比较，通过双指针实时扩展和收缩窗口。时间复杂度为 $O((n + m) \times \min(n, m))$，其中 $n$ 和 $m$ 是数组长度。空间复杂度为 $O(1)$，仅需常数额外空间。

Java 代码实现

以下是完整的 Java 解决方案。代码注释详细解释了每一步：

public class LongestRepeatingSubarray {
    public int findLength(int[] A, int[] B) {
        int n = A.length;
        int m = B.length;
        int maxLen = 0;  // 存储最大长度
        
        // 遍历所有可能的偏移量 d
        for (int d = -(m - 1); d < n; d++) {
            int i = Math.max(d, 0);  // 指针 i 指向 A 的起始索引
            int j = Math.max(-d, 0); // 指针 j 指向 B 的起始索引
            int currentLen = 0;       // 当前匹配长度
            
            // 使用指针 k 扩展窗口，比较元素
            while (i < n && j < m) {
                if (A[i] == B[j]) {
                    currentLen++;      // 元素相等，增加长度
                    maxLen = Math.max(maxLen, currentLen); // 更新最大值
                } else {
                    currentLen = 0;   // 元素不等，重置长度
                }
                i++;  // 移动指针
                j++;
            }
        }
        return maxLen;
    }
}

代码解释：

• 初始化：获取数组长度 $n$ 和 $m$，初始化 maxLen 存储结果。
• 偏移量循环：变量 $d$ 表示 $A$ 相对于 $B$ 的偏移。例如 $d = -1$ 表示 $B$ 的起始索引比 $A$ 早一位。
• 指针设置：i 和 j 是双指针，分别指向 $A$ 和 $B$ 的当前比较位置。Math.max 确保索引不越界。
• 窗口比较：while 循环中，指针同步移动（$k$ 隐含在 i++ 和 j++ 中）。如果 $A[i] == B[j]$，则累积 currentLen；否则重置为 0。
• 更新结果：每次匹配时，用 Math.max 更新 maxLen。
• 边界处理：循环条件 i < n && j < m 防止数组越界。

复杂度分析

• 时间复杂度：外层循环次数为 $O(n + m)$，内层 while 循环在每次偏移量下最多运行 $O(\min(n, m))$ 次。因此总时间复杂度为 $O((n + m) \times \min(n, m))$。在平均情况下，这比暴力法（$O(n \times m)$）更优。
• 空间复杂度：$O(1)$，仅使用固定数量的变量。

测试示例

验证代码的正确性：

public static void main(String[] args) {
    LongestRepeatingSubarray solver = new LongestRepeatingSubarray();
    int[] A1 = {1,2,3,2,1}, B1 = {3,2,1,4,7};
    System.out.println(solver.findLength(A1, B1)); // 输出 3
    
    int[] A2 = {0,0,0,0,0}, B2 = {0,0,0,0,0};
    System.out.println(solver.findLength(A2, B2)); // 输出 5
    
    int[] A3 = {1,2,3}, B3 = {4,5,6};
    System.out.println(solver.findLength(A3, B3)); // 输出 0
}

总结

通过滑动窗口和双指针技术，我们优雅地解决了「最长重复子数组」问题。该方法在 Java 中实现简单，代码可读性强，适用于实际开发。核心在于遍历偏移量和利用双指针动态比较元素，避免了复杂的数据结构。你可以扩展此思路到其他子数组问题，如最长公共子序列（需调整连续性约束）。练习时，尝试优化代码或处理边界情况，以加深理解。