具有相等总和的两个数组中的最大跨度

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],然后问题变成找到i,j,哪个sum(c[i], c[i+1], ..., c[j]) = 0,和最大j - i.

第二个让d[0] = 0,d[i + 1] = d[i] + c[i], i >= 0然后问题变成找到i,j,哪个d[j + 1] == d[i],和最大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
    }
  }
}

Answer 2

这是一个O(n)解决方案。

我使用的事实是sum[i..j] = sum[j] - sum[i - 1].

我保留每个找到的总和的最左边的位置。

    int convertToPositiveIndex(int index) {
        return index + N;
    } 

    int mostLeft[2 * N + 1];
    memset(mostLeft, -1, sizeof(mostLeft));

    int bestLen = 0, bestStart = -1, bestEnd = -1;

    int sumA = 0, sumB = 0;
    for (int i = 0; i < N; i++) {
        sumA += A[i];
        sumB += B[i];

        int diff = sumA - sumB;
        int diffIndex = convertToPositiveIndex(diff);

        if (mostLeft[diffIndex] != -1) {
            //we have found the sequence mostLeft[diffIndex] + 1 ... i
            //now just compare it with the best one found so far 
            int currentLen = i - mostLeft[diffIndex];
            if (currentLen > bestLen) {
                bestLen = currentLen;
                bestStart = mostLeft[diffIndex] + 1;
                bestEnd = i;
            }
        }

        if (mostLeft[diffIndex] == -1) {
            mostLeft[diffIndex] = i;
        }
    }

cout << bestStart << " " << bestEnd << " " << bestLen << endl;

PSmostLeft数组是2 * N + 1，因为有负数。