最长重复子数组（有重叠）

Question

向各位用户问好，希望您度过愉快的一天。我有疑问。

给定一个任意数字的数组，我希望快速[时间和空间复杂度至少低于 O(n²)，n = 数组长度]找到重复的最长子数组（数组中元素的连续段） （出现多次，或至少两次）。请不要假设数组中数字的任何界限，除了所有值都是有效的 JavaScript 数字，并且

isFinite

对于数组中的每个数字都成立

允许重叠，即允许子数组在其内部部分出现。例如，在数组

[1, 2, 1, 2, 1, 2]

中，最长的重复子数组是

[1, 2, 1, 2]

。看这里

[1, 2, 1, 2, 1, 2]
^         ^        occurence #1
       ^        ^  occurence #2

这两个事件重叠，但只要两个事件的起始索引或结束索引不同就可以。

如果存在多个不同的重复子数组，并且它们都具有最长的长度，则答案可以是其中任何一个。然而，我怀疑任何能够找到一个答案的方法都可以同样轻松地找到所有答案。 此场景的一个示例是数组

[1, 1, 2, 2]

。子数组

[1]

和

[2]

都出现了两次。其中任何一个都可能作为结果返回。

最后，如果没有子数组出现多次，则答案为

[]

（空数组）。

我最近遇到了问题在数组中查找重复序列，但所有答案都慢得离谱。每个人都使用 o(n3) 解，o(n2) 中只有一个答案。我正在寻找一种可以在几秒钟内处理长度高达几十万（100,000）的数组的方法。时间复杂度至少为次二次方。

抱歉问了这么长的问题，如果有任何不清楚的地方请告诉我。如果您有一个想法但不是完整的解决方案，请将其放在评论中，它仍然对我有帮助。先谢谢大家了

如果有帮助的话，我做了更多例子：

数组	结果
[1, 2, 5, 7, 1, 2, 4, 5]	[1, 2]
[9, 7, 0, 1, 6, 3, 6, 5, 2, 1, 6, 3, 8, 3, 6, 1, 6, 3]	[1, 6, 3]
[1, 2, 1, 2, 7, 0, -1, 7, 0, -1]	[7, 0, -1]
[1, 1, 1, 1]	[1, 1, 1]
[1, 1, 1]	[1, 1]
[1, 2, 3, 4, 2, 5]	[2]
[1, 2, 3, 4, 5]	[]
[1, 6, 2, 1, 6, 2, 1, 5]	[1, 6, 2, 1]

这里有一个生成数组大小为 100,000 的大型测试用例的函数供参考，答案是 [1, 2, 3, ..., 100]（从 1 到 100 的 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;
}

Answer 1

看起来很简单，你可以通过一些循环来实现。这未经测试，但应该有效

var 求解=（输入）=> { var ans、s、s2、ii、_ans s = 0 答案=[] while (s < input.length) { s2 = s + 1 while (s2 < input.length) { ii = 0 _ans = [] while (ii + s2 < input.length) { if (input[s+ii] != input[s2+ii]) { break } else { _ans.push(input[s+ii]) ii++ } } if (ii > ans.length) { console.log(s, s2, ii, _ans) 安斯=_安斯 } s2++ } s++ } 返回答案 }

hth