arrays - 计算相似度数大于 K 的子数组

Question

两个数组 X 和 Y 的相似度数，每个数组的大小为 N，定义为索引对 (i,j) 的数量，使得 X[i]=Y[j] ，对于 1<=i,j

现在给定两个数组，大小为 N 和 M。我们需要从这两个数组中找到大小相等的子数组的数量，使得每个子数组对的相似数大于或等于给定数字 K。

例如，假设我们有 N=3、M=3、K=1 并且数组是 [1,3,4] 和 [1,5,3] 那么这里的答案是 6

解释:

({1},{1})
({3},{3})
({1,3},{1,5})
({1,3},{5,3})
({3,4},{5,3})
({1,3,4},{1,5,3})

所以 ans = 6

如何解决给定大小为 N、M 和给定整数 K 的数组。元素个数不能超过2000个，K也小于N*M

方法:从大小为 N 的数组 1 中形成所有子数组，这些子数组将为 N*(N+1)/2 并且对于大小为 M 的数组 2 相同。然后尝试找到每个子数组对之间的相似度数。但这是非常未优化的方式。有什么更好的方法可以解决这个问题？我认为动态规划可以用来解决这个问题。有什么建议吗？

对于 {1,1,2} 和 {1,1,3} 和 K=1

{[1(1)],[1(1)]}
{[1(1)],[1(2)]}
{[1(2)],[1(1)]}
{[1(2)],[1(2)]}
{[1(1),1(2)],[1(1)]}
{[1(1),1(2)],[1(2)]}
{[1(1)],[1(1),1(2)]}
{[1(2)],[1(1),1(2)]}
{[1(1),1(2)],[1(1),1(2)]}
{[1(2),2],[1(2),3]}
{[1(1),1(2),2],[1(1),1(2),3]}

Answer 1

由于比赛已经结束，为了完整起见，这里是我对那里的编辑答案的理解(我从中学到了很多东西)。假设我们有一个 O(1) time 方法计算两个连续子数组的相似性，每个子数组一个，长度为 l .然后，对于每对索引，(i, j) ，我们可以二分查找最小的 l (延伸，说到他们的左边)满足相似性k . (一旦我们有了最小的 l ，我们就知道任何更大的 l 也有足够的相似性，我们可以在 O(1) 时间内添加这些计数。)在这种情况下，总时间将是 O(M * N * log(max (M,N)) .

好吧，事实证明有一种方法可以计算 O(1) 中两个连续子数组的相似度。 :矩阵前缀和。在矩阵中，A ;其中每个条目，A(i,j) , 是 1如果第一个数组的 i第 th 个元素等于第二个数组的 j第元素和 0否则; A 中元素的总和在矩形中A(i-l, j-l) , A(i,j) (从左上角到右下角)就是这样。我们可以在 O(1) 中计算该总和给定O(M*N) 矩阵前缀和的时间预处理。