寻找最长允许重叠重复子数组：亚二次复杂度JS实现需求

问题需求 #

给定任意由JavaScript数值组成的数组，需要以时间、空间复杂度低于O(n²)（亚二次）的效率，查找其中最长的重复子数组：

• 子数组是数组的连续片段，至少出现两次
• 允许重叠，只要两次出现的起止索引不完全相同即可（例如[1,2,1,2,1,2]中最长重复子数组为[1,2,1,2]）
• 若存在多个长度相同的最长重复子数组，返回任意一个即可（如[1,1,2,2]中返回[1]或[2]都可以）
• 若无重复子数组，返回空数组[]

现有方案多为O(n³)或仅O(n²)复杂度，无法高效处理长度达100,000的数组，需实现可在数秒内完成此类规模数据处理的方案，并提供JavaScript示例代码。

测试用例 #

大规模测试用例生成函数 #

生成长度为100,000的数组，预期最长重复子数组为[1,2,...,100]：

function make_case() {
    let array = [];
    let number = 200;
    for (let i = 0; i < 500; i++) {
        array.push(number); array.push(number);
        number++;
    }
    for (let i = 1; i < 101; i++) {
        array.push(i);
    }
    for (let i = 0; i < 1700; i++) {
        array.push(number); array.push(number);
        number++;
    }
    for (let i = 1; i < 101; i++) {
        array.push(i);
    }
    for (let i = 0; i < (100_000 - 500 * 2 - 100 - 1700 * 2 - 100) / 2; i++) {
        array.push(number); array.push(number);
        number++;
    }
    return array;
}

极端测试用例 #

输入new Array(100_000).fill(0)，预期结果为包含99999个0的数组。

解决方案：二分查找+滚动哈希（Rabin-Karp） #

采用二分查找确定最长重复子数组的长度，结合滚动哈希快速判断某一长度的子数组是否存在重复。整体时间复杂度为O(n log n)，空间复杂度为O(n)，满足亚二次要求。

核心思路 #

1. 二分查找长度范围：最长可能的重复子数组长度范围是[1, n-1]（n为数组长度），若不存在则返回空数组。
2. 滚动哈希验证：对每个候选长度L，计算所有长度为L的子数组的哈希值，若存在重复的哈希值（需额外验证避免哈希碰撞），说明存在该长度的重复子数组，尝试寻找更长的；否则尝试更短的。
3. 提取结果：找到最长的有效长度后，遍历数组找到对应的重复子数组并返回。

JavaScript实现代码 #

function longestRepeatingSubarray(arr) {
    const n = arr.length;
    if (n < 2) return [];

    // 滚动哈希参数，选大质数减少碰撞概率
    const base = 911382629;
    const mod = 10**18 + 3;

    // 计算base的幂次：base^(L-1) mod mod，用于滚动哈希
    function computePower(L) {
        let power = 1;
        for (let i = 0; i < L - 1; i++) {
            power = (power * base) % mod;
        }
        return power;
    }

    // 检查是否存在长度为L的重复子数组，返回第一次找到的起始索引对
    function hasDuplicate(L) {
        if (L === 0) return [0, 0];
        const power = computePower(L);
        let currentHash = 0;
        const hashMap = new Map();

        // 计算第一个子数组的哈希
        for (let i = 0; i < L; i++) {
            currentHash = (currentHash * base + arr[i]) % mod;
        }
        hashMap.set(currentHash, [0]);

        // 滚动计算后续子数组的哈希
        for (let i = L; i < n; i++) {
            // 移除左端元素的贡献，加入右端元素
            currentHash = (currentHash - arr[i - L] * power % mod + mod) % mod;
            currentHash = (currentHash * base + arr[i]) % mod;

            if (hashMap.has(currentHash)) {
                // 验证哈希对应的子数组是否真的相同，避免碰撞
                const starts = hashMap.get(currentHash);
                for (const start of starts) {
                    let match = true;
                    for (let j = 0; j < L; j++) {
                        if (arr[start + j] !== arr[i - L + 1 + j]) {
                            match = false;
                            break;
                        }
                    }
                    if (match) {
                        return [start, i - L + 1];
                    }
                }
                starts.push(i - L + 1);
            } else {
                hashMap.set(currentHash, [i - L + 1]);
            }
        }
        return null;
    }

    // 二分查找最长长度
    let left = 1, right = n - 1;
    let bestLen = 0;
    let bestIndices = null;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const indices = hasDuplicate(mid);
        if (indices) {
            bestLen = mid;
            bestIndices = indices;
            left = mid + 1; // 尝试更长的长度
        } else {
            right = mid - 1; // 尝试更短的长度
        }
    }

    if (bestLen === 0) return [];
    // 返回第一个出现的重复子数组
    return arr.slice(bestIndices[0], bestIndices[0] + bestLen);
}

// 测试示例
console.log(longestRepeatingSubarray([1, 2, 5, 7, 1, 2, 4, 5])); // [1,2]
console.log(longestRepeatingSubarray([9, 7, 0, 1, 6, 3, 6, 5, 2, 1, 6, 3, 8, 3, 6, 1, 6, 3])); // [1,6,3]
console.log(longestRepeatingSubarray([1, 2, 1, 2, 7, 0, -1, 7, 0, -1])); // [7,0,-1]
console.log(longestRepeatingSubarray([1,1,1,1])); // [1,1,1]
console.log(longestRepeatingSubarray([1,1,1])); // [1,1]
console.log(longestRepeatingSubarray([1,2,3,4,2,5])); // [2]
console.log(longestRepeatingSubarray([1,2,3,4,5])); // []
console.log(longestRepeatingSubarray([1,6,2,1,6,2,1,5])); // [1,6,2,1]

// 测试大规模用例（取消注释运行）
// const largeArr = make_case();
// console.log(longestRepeatingSubarray(largeArr).length); // 100

// 测试全0数组（取消注释运行）
// const allZero = new Array(100_000).fill(0);
// console.log(longestRepeatingSubarray(allZero).length); // 99999

说明 #

• 滚动哈希使用大质数作为基数和模数，大幅降低碰撞概率，同时在哈希冲突时通过直接比较子数组确保结果正确性。
• 二分查找将问题分解为O(log n)次哈希验证，每次验证的时间复杂度为O(n)，整体达到O(n log n)的亚二次复杂度。
• 对于全0等极端情况，代码能正确识别最长可能的重复子数组。

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