C++で0と1の個数が等しい部分配列を数える方法

0と1のみを含む配列 arr[] が与えられます。この課題のゴールは、0と1の個数が等しくなっているすべての部分配列(サブアレイ)の総数を求めることです。例えば、配列が [1,0,0] である場合、条件を満たす部分配列は [1,0] のみとなります。

具体的な例で理解していきましょう。

入力 − arr[] = { 0, 0, 1, 1, 1, 0 }

出力 − 0と1の個数が等しい部分配列の数:4

説明 − 条件を満たす部分配列は以下の通りです。

arr[0〜3] = [0,0,1,1]
arr[1〜2] = [0,1]
arr[4〜5] = [1,0]
arr[0〜5] = [0,0,1,1,1,0]

入力 − arr[] = { 0, 1, 1, 1, 1 }

出力 − 0と1の個数が等しい部分配列の数:1

説明 − 条件を満たす部分配列は arr[0〜1] = [0,1] のみです。

プログラムで使用するアプローチ

2つの for ループを使用して配列を走査し、考えられるすべての部分配列を生成します。外側のループは i=0 から i<=size-1 まで、内側のループは j=i から j<=size-1 まで繰り返し、arr[i] から arr[j] までの範囲を部分配列として扱います。各部分配列に含まれる 0 と 1 の出現回数をそれぞれカウントし、両者が等しければ答えのカウントを1増やします。

• 数値の配列 arr[] を用意します。

• 関数 sub_zeroes_ones(int arr[], int size) は配列を受け取り、0と1の個数が等しい部分配列の数を返します。

• カウント用変数 count の初期値を 0 とします。

• i=0 から i<=size-1 まで、j=i から j<=size-1 までの二重ループで配列を走査します。

• 部分配列 arr[i]〜arr[j] に含まれる 0 と 1 の個数を記録するため、変数 total_0 と total_1 を 0 で初期化します。

• arr[j] の値を判定し、0 であれば total_0 を、1 であれば total_1 をインクリメントします。

• total_0 == total_1 が成り立てば count をインクリメントします(その部分配列には同数の 0 と 1 が含まれています)。

• すべてのループが終了したら、count を結果として返します。

計算量に関する補足

この手法ではすべての部分配列の組み合わせを調べるため、時間計算量は O(n²) となります。配列サイズ n が大きくなると処理に時間がかかる点に注意してください。より高速な解法を求める場合は、0 を -1 に読み替えて累積和(プレフィックスサム)をハッシュマップで管理することで、O(n) で求める最適化アプローチも知られています。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int sub_zeroes_ones(int arr[], int size){
    int count = 0;
    for (int i = 0; i <= size - 1; i++){
        int total_0 = 0;
        int total_1 = 0;
        for (int j = i; j <= size - 1; j++){
            if (arr[j] == 0){
                total_0++;
            }
            else if (arr[j] == 1){
                total_1++;
            }
            if(total_0 == total_1){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = {0, 1, 1, 0, 0};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Count of subarrays with equal number of 1’s and 0’s are: "<<sub_zeroes_ones(arr, size);
}

出力

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

Count of subarrays with equal number of 1’s and 0’s are: 4