C++で0と1の数が等しい最大部分配列を見つける方法

はじめに

このチュートリアルでは、C++を使って0と1の個数が等しい最大の部分配列を見つけるアルゴリズムを解説します。与えられた配列の中から、0と1が同数ずつ含まれる最長の連続した部分配列を求める、定番のアルゴリズム問題です。

アルゴリズムの考え方

この問題を効率的に解くポイントは、配列内のすべての 0 を -1 に置き換える ことです。そうすることで、「0と1の個数が等しい部分配列を探す」という問題を「合計が0になる部分配列を探す」問題に言い換えられます。さらに、累積和とハッシュマップ（unordered_map）を組み合わせることで、計算量 O(n) という高速な処理が可能になります。

プログラムの手順

• 配列を初期化します。
• 配列内のすべての 0 を -1 に変換します。
• 過去のインデックスを保存するための空のマップを用意します。
• 合計値 sum を 0、最大長 maxLength を 0、終了インデックス endingIndex を -1 で初期化します。
• n 回繰り返すループを記述します。
  • 現在の要素を sum に加算します。
  • sum が 0 と等しい場合：
    • maxLength を i + 1 に更新します。
    • endingIndex を i に更新します。
  • sum が過去の合計のマップに存在し、かつ i - previousIndexes[sum] が maxLength より大きい場合：
    • maxLength と endingIndex を更新します。
  • それ以外の場合は、sum とその時点のインデックスを過去のインデックスのマップに追加します。
• 開始インデックス（endingIndex - maxLength + 1）と終了インデックス（endingIndex）を出力します。

コード例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

// 0と1の数が等しい最大の部分配列を見つける関数
void findTheSubArray(int arr[], int n) {
    unordered_map<int, int> previousIndexes;
    int sum = 0, maxLength = 0, endingIndex = -1;

    // すべての0を-1に変換する
    for (int i = 0; i < n; i++) {
        arr[i] = arr[i] == 0 ? -1 : 1;
    }

    for (int i = 0; i < n; i++) {
        sum += arr[i];

        // 先頭からの累積和が0の場合、それが最長の候補となる
        if (sum == 0) {
            maxLength = i + 1;
            endingIndex = i;
        }

        // 同じ累積和が過去に出現している場合
        if (previousIndexes.find(sum) != previousIndexes.end()) {
            if (maxLength < i - previousIndexes[sum]) {
                maxLength = i - previousIndexes[sum];
                endingIndex = i;
            }
        } else {
            previousIndexes[sum] = i;
        }
    }

    cout << endingIndex - maxLength + 1 << " " << endingIndex << endl;
}

int main() {
    int arr[] = { 1, 1, 0, 0, 0, 1, 1, 1, 0 };
    findTheSubArray(arr, 9);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

1 8

この結果は、インデックス 1 から 8 までの部分配列 { 1, 0, 0, 0, 1, 1, 1, 0 } に 0 と 1 がそれぞれ 4 個ずつ含まれており、条件を満たす最長の部分配列であることを示しています。

まとめ

0 を -1 に変換したうえで累積和とハッシュマップを活用することで、0と1の個数が等しい最大の部分配列を線形時間 O(n) で効率的に求められます。本チュートリアルについてご質問がある場合は、コメント欄でお知らせください。