algorithm - 总和相等的两个数组中的最大跨度

Question

这是编程难题。我们有两个数组 A 和 B。都只包含 0 和 1。

我们必须有两个索引 i, j 使得

 a[i] + a[i+1] + .... a[j] = b[i] + b[i+1] + ... b[j]. 

我们还必须最大化 i 和 j 之间的差异。寻找 O(n) 解决方案。

我找到了 O(n^2) 的解决方案，但没有得到 O(n)。

Answer 1

最佳解决方案是O(n)

首先让c[i] = a[i] - b[i]，然后问题变成find i, j，这sum(c[i], c[i+1], ..., c[j]) = 0 和 max j - i。

第二令d[0] = 0, d[i + 1] = d[i] + c[i], i >= 0, 然后提问成为查找 i、j，其中 d[j + 1] == d[i]，以及 max j - i.

d的值在[-n, n]范围内，所以我们可以用下面的代码来求答案

answer = 0, answer_i = 0, answer_j = 0
sumHash[2n + 1] set to -1
for (x <- 0 to n) {
  if (sumHash[d[x]] == -1) {
    sumHash[d[x]] = x
  } else {
    y = sumHash[d[x]]
    // find one answer (y, x), compare to current best
    if (x - y > answer) {
      answer = x - y
      answer_i = y
      answer_j = y
    }
  }
}