GFG竞赛题《Geek's Journey》代码错误排查及解法咨询

问题描述 #

给定两个数组：

• 长度为n的geeksTown数组：表示小镇建筑高度
• 长度为m的journey数组：表示旅途中看到的建筑高度

当journey中出现与geeksTown完全匹配的连续子数组时，Geek会感到开心。现有q个[l,r]形式的查询，需统计每个查询区间内Geek感到开心的次数。

示例输入输出 #

示例1

输入: n = 4, geeksTown[] = {3, 0, 1, 9}, m = 11, journey[] = {1, 3, 0, 1, 9, 1, 7, 3, 0, 1, 9}, q = 4, queries[] = [ [0, 3], [1, 5], [1, 10], [7, 9] ]
输出: 0 1 2 0

示例2

输入: n = 2, geeksTown[] = {2, 2}, m = 6, journey[] = {2, 2, 2, 2, 2, 2}, q = 3, queries[] = [ [0, 2], [1, 4], [0, 5] ]
输出: 2 3 5

现有代码的错误分析 #

你用Deque实现滑动窗口的思路方向没错，但代码存在多处逻辑错误：

1. 初始窗口未检查匹配
   代码初始化了前n个元素的窗口，但没有先判断这个窗口是否和geeksTown匹配，直接进入后续循环，导致漏掉了起始位置为0的匹配情况。

2. 匹配失败后的窗口滑动逻辑错误
   当匹配到中间元素失败时，代码直接将i跟着j一起递增，导致窗口一次性滑动了多个位置，跳过了很多可能的匹配起点。比如如果匹配到第2个元素失败，正确的做法应该是窗口只滑动1位，而不是直接滑动j位。

3. Deque的操作破坏窗口连续性
   在匹配过程中，每匹配一个元素就从Deque头部移除并添加新元素，这会导致窗口的状态被打乱。当匹配失败时，无法恢复到之前的窗口状态，后续的匹配判断完全错误。

4. dp数组标记位置错误
   当完成一次完整匹配时，dp[i-n] = true的计算逻辑混乱。比如一次匹配的结束索引应该是i-1（因为i已经递增到了下一个位置），对应的起始索引是i-n，如果dp数组标记的是结束索引，那应该是dp[i-1] = true，而非dp[i-n]，这会导致后续查询统计完全错误。

5. 查询时的边界处理问题
   即使dp数组标记正确，当前查询的边界计算也存在逻辑漏洞。比如当queries[i][0] + n -1超过r时，应该直接返回0，但代码仍会进入循环，不过这属于小问题，核心还是前面的匹配逻辑错误。

可行解法 #

解法1：KMP算法 + 前缀和数组 #

这是效率最高的解法，适合处理大规模数据：

1. 构建模式串的前缀函数：用KMP算法的前缀函数处理geeksTown数组，生成前缀数组pi，用于在匹配过程中快速回退。
2. 遍历journey数组找匹配：用KMP的匹配逻辑遍历journey，记录所有匹配的结束位置。
3. 构建前缀和数组：创建一个prefix数组，prefix[i]表示前i个位置中匹配的次数，这样查询[l,r]时，只需计算满足结束索引在[l+n-1, r]范围内的匹配数量，通过前缀和可以O(1)得到结果。

Java实现示例：

class Solution {
    public int[] geeksJourney(int geeksTown[], int n, int journey[], int m, int queries[][], int q) {
        if (n > m) {
            return new int[q];
        }
        
        // 步骤1：构建KMP前缀函数
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i-1];
            while (j > 0 && geeksTown[i] != geeksTown[j]) {
                j = pi[j-1];
            }
            if (geeksTown[i] == geeksTown[j]) {
                j++;
            }
            pi[i] = j;
        }
        
        // 步骤2：用KMP找所有匹配的结束位置
        int[] matchCount = new int[m]; 
        int j = 0;
        for (int i = 0; i < m; i++) {
            while (j > 0 && journey[i] != geeksTown[j]) {
                j = pi[j-1];
            }
            if (journey[i] == geeksTown[j]) {
                j++;
            }
            if (j == n) {
                matchCount[i] = 1;
                j = pi[j-1]; // 回退，寻找下一个可能的匹配
            }
        }
        
        // 步骤3：构建前缀和数组
        int[] prefix = new int[m+1];
        for (int i = 0; i < m; i++) {
            prefix[i+1] = prefix[i] + matchCount[i];
        }
        
        // 处理查询
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int startEnd = l + n -1;
            if (startEnd > r) {
                ans[i] = 0;
                continue;
            }
            ans[i] = prefix[r+1] - prefix[startEnd];
        }
        return ans;
    }
}

解法2：滑动窗口 + 滚动哈希 #

通过计算窗口的哈希值，快速比较journey的窗口和geeksTown的哈希值是否相等：

1. 计算geeksTown的哈希值。
2. 计算journey中前n个元素的哈希值，和目标哈希比较，记录匹配。
3. 滑动窗口，每次移除窗口最左元素的哈希贡献，添加新元素的哈希贡献，重新比较哈希值。
4. 同样用前缀和数组处理查询。

这种方法实现简单，但要注意哈希冲突的问题，可以用双哈希（两个不同的哈希函数）来降低冲突概率。

内容的提问来源于stack exchange，提问作者Tejas S