如何在JavaScript中识别数组的重复模式（含非起始位置）

嘿，这个问题很实用——要在数组里找出是否存在重复的连续元素模式，而且模式可以从任意索引开始，对吧？我来分享几个从基础到优化的思路，重点讲最适合大多数场景的高效实现。

先明确问题定义 #

我们要找的是至少一段长度≥1的连续子序列，在数组中出现过至少两次（起始位置不同，允许重叠）。比如你给的示例数组[1,5,7,5,13,8,1,7,3,8,5,2,1,5,7]，开头的[1,5,7]和末尾的[1,5,7]就是重复模式。

基础思路（暴力法） #

最直接的方式是枚举所有可能的子序列，然后检查是否有重复。但这种方法的时间复杂度是O(n³)（枚举起始位置、长度，再比较子序列），对于稍大的数组就会很慢，显然不是最优解。

最优方案：Rabin-Karp滚动哈希法 #

滚动哈希（也叫Rabin-Karp算法）能把每个子序列的哈希计算时间降到O(1)（除了第一个子序列），大幅提升效率。核心思路是用哈希值快速判断子序列是否可能重复，再验证避免哈希碰撞。

实现步骤 #

1. 特殊情况处理：数组长度小于2时直接返回false；先检查是否有重复元素（长度1的模式），有就直接返回true。
2. 滚动哈希计算：
   • 选择一个大质数作为基数，再选一个大模数避免哈希溢出（用BigInt更稳妥）。
   • 对每个可能的模式长度L，计算所有长度为L的子序列的哈希值，用哈希表记录哈希对应的起始索引。
   • 当发现哈希重复时，实际比较两个子序列是否真的相等（避免哈希碰撞），相等则返回true。
3. 处理长模式：对于长度超过数组一半的模式，直接比较开头和末尾的重叠子序列即可。

代码实现（JavaScript） #

function hasRepeatingPattern(arr) {
    const n = arr.length;
    if (n < 2) return false;

    // 快速检查长度为1的重复模式（重复元素）
    const singleElementSet = new Set();
    for (const num of arr) {
        if (singleElementSet.has(num)) return true;
        singleElementSet.add(num);
    }

    // Rabin-Karp滚动哈希配置：大质数基数+大模数
    const base = 911382629n;
    const mod = 10n ** 18n + 3n;

    // 检查长度2到n/2的模式
    for (let L = 2; L <= Math.floor(n / 2); L++) {
        const hashMap = new Map();
        // 计算第一个窗口的哈希
        let currentHash = 0n;
        for (let i = 0; i < L; i++) {
            currentHash = (currentHash * base + BigInt(arr[i])) % mod;
        }
        hashMap.set(currentHash, [0]);

        // 计算base^L mod mod，用于滚动更新哈希
        let baseL = 1n;
        for (let i = 0; i < L; i++) {
            baseL = (baseL * base) % mod;
        }

        // 滚动计算后续窗口的哈希
        for (let start = 1; start <= n - L; start++) {
            // 更新当前哈希：移除左端元素，加入右端元素
            currentHash = (currentHash * base - BigInt(arr[start - 1]) * baseL + BigInt(arr[start + L - 1])) % mod;
            // 确保哈希为正数
            if (currentHash < 0n) currentHash += mod;

            if (hashMap.has(currentHash)) {
                // 验证哈希对应的子序列是否真的相等（避免碰撞）
                const prevStarts = hashMap.get(currentHash);
                for (const prevStart of prevStarts) {
                    let isEqual = true;
                    for (let i = 0; i < L; i++) {
                        if (arr[prevStart + i] !== arr[start + i]) {
                            isEqual = false;
                            break;
                        }
                    }
                    if (isEqual) return true;
                }
                prevStarts.push(start);
            } else {
                hashMap.set(currentHash, [start]);
            }
        }
    }

    // 检查长度超过n/2的模式（只能是开头和末尾的重叠子序列）
    for (let L = Math.floor(n / 2) + 1; L < n; L++) {
        const start2 = n - L;
        let isEqual = true;
        for (let i = 0; i < L; i++) {
            if (arr[i] !== arr[start2 + i]) {
                isEqual = false;
                break;
            }
        }
        if (isEqual) return true;
    }

    return false;
}

// 测试示例数组
const arr = [1, 5, 7, 5, 13, 8, 1, 7, 3, 8, 5, 2, 1, 5, 7];
console.log(hasRepeatingPattern(arr)); // 输出true

方案优势 #

• 时间效率：平均情况远优于暴力法，短模式会提前返回；最坏情况O(n²)，但实际中很少触发。
• 空间效率：仅用O(n)空间存储哈希表，内存占用可控。
• 可靠性：通过子序列验证避免哈希碰撞，结果准确。

进阶优化：后缀自动机 #

如果处理超大规模数组（比如百万级元素），可以用后缀自动机，时间复杂度O(n)，但实现难度较高，适合专业场景。

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