Максимальный интервал в двух массивах с равной суммой

Ответ 1

Вот решение 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;

P.S. mostLeft массив 2 * N + 1, из-за негативов.

Ответ 2

Лучшим решением является 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, затем вопрос станет find 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
    }
  }
}

Ответ 3

В принципе, мое решение выглядит следующим образом.

Возьмите переменную, чтобы позаботиться о разнице с самого начала.

int current = 0;
for index from 0 to length
    if a[i] == 0 && b[i] == 1
        current--;
    else if a[i] == 1 && b[i] == 0
        current++;
    else
        // nothing;

Найдите позиции, в которых переменная имеет одно и то же значение, что означает, что между ними равны 1 и 0.

Псевдокод:

Вот мое основное решение:

int length = min (a.length, b.length);
int start[] = {-1 ... -1}; // from -length to length
start[0] = -1;
int count[] = {0 ... 0};   // from -length to length
int current = 0;
for (int i = 0; i < length; i++) {
    if (a[i] == 0 && b[i] == 1)
        current--;
    else if (a[i] == 1 && b[i] == 0)
        current++;
    else
        ; // nothing

    if (start[current] == -1) // index can go negative here, take care
        start[current] = current;
    else
        count[current] = i - start[current];
}
return max_in(count[]);

Ответ 4

Это довольно простое решение O (N):

let sa = [s1, s2, s3.. sn] где si = sum(a[0:i]) и аналогичный для sb

тогда sum(a[i:j]) = sa[j]-sa[i] и sum(b[i:j]) = sb[j] - sb[i]

Заметим, что поскольку суммы только возрастают на 1 каждый раз, мы знаем 0 <= sb[N], sa[N] <=N

difference_array = [d1, d2, .. dn] где di = sb[i] - sa[i] <= N

обратите внимание, если di = dj, то sb[i] - sa[i] = sb[j] - sa[j], что означает, что они имеют одинаковую сумму (переупорядочивают, чтобы получить sum(b[i:j]) and sum(a[i:j]) сверху).

Теперь для каждой разницы нам понадобится его максимальное расположение позиции и минимальное расположение позиции

Теперь для каждой разности di разность между max - min, является секцией i-j равной суммы. Найдите максимальное значение max-min, и все готово.

пример кода, который должен работать:

a = []
b = []
sa = [0]
sb = [0]
for i in a:
    sa.append(sa[-1] + i)
for i in b:
    sb.append(sb[-1] + i)

diff = [sai-sbi for sai, sbi in zip(sa, sb)]
min_diff_pos = {}
max_diff_pos = {}
for pos, d in enumerate(diff):
    if d in min_diff_pos:
        max_diff_pos[d] = pos
    else:
        min_diff_pos[d] = pos

ans = min(max_diff_pos[d] - min_diff_pos[d] for d in diff)