这是编程难题。我们有两个数组 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)
。
最佳答案
最佳解决方案是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
}
}
}
关于algorithm - 总和相等的两个数组中的最大跨度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13154401/