algorithm - 合計が等しい 2 つの配列の最大スパン

Question

プログラミングパズルです。2 つの配列 A と B があります。どちらも 0 と 1 のみを含みます。

となるような 2 つのインデックス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)

最初に let c[i] = a[i] - b[i]、次に質問が find i、j、 which sum(c[i], c[i+1], ..., c[j]) = 0、および max になりj - iます。

2 番目の let d[0] = 0、d[i + 1] = d[i] + c[i], i >= 0、次に質問は find i、j、 which 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
    }
  }
}

Answer 2

基本的に、私の解決策は次のようになります。

最初から違いを処理するために変数を使用します。

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[]);

Answer 3

これはかなり単純な O(N) ソリューションです。

let sa = [s1, s2, s3.. sn]wheresi = sum(a[0:i])および類似の forsb

それから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 の差は、等しい合計の ij セクションです。最大最大最小値を見つければ完了です。

動作するはずのサンプルコード:

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)

Answer 4

これが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、ネガのためです。