java - 找到最长的重复子数组

Question

给定一个数组 a[0..N-1] 0 < N < 10^5 之间的整数，求最优时间和空间内最长且重复次数最多的子数组的大小。我正在考虑使用 HashMap 来存储数字开始的索引，并开始检查每个索引它可以形成的可能的子数组。但这似乎效率低下，所以我想听听一些关于如何解决这个问题的意见。

示例:

输入a = [0,1,2,1,4,1,2,1,0,5]
预期输出:Most Repeated: [1,2,1]; Size: 3

Answer 1

众所周知，此类问题的方法很幼稚 - 需要花费大量时间并对所有可能的解决方案进行强力搜索。

显然，您并不是在寻找那个。每当你遇到这种情况时，答案总是动态规划。它相当广泛，对于初学者来说很难，但在计算机科学中非常重要。这意味着，我无法在这个答案中涵盖它。

但这里有一个解决此问题的方法。

由于 A 和 B 的公共(public)子数组必须从某个 A[i] 和 B[j] 开始，因此令 dp[i][j] 是A[i:]和B[j:]的最长公共(public)前缀。每当A[i] == B[j]时，我们就知道dp[i][j] = dp[i+1][j+1] + 1。另外，答案是所有 i、j 的 max(dp[i][j])。

我们可以根据这个递推式进行自下而上的动态规划来寻找答案。我们的循环不变式是，对于任何较大的 i、j，答案已经正确计算并存储在 dp 中。

希望这有帮助。祝你好运。