【C++】2つの指定された要素の出現回数が等しい部分配列を数える方法

はじめに

整数型の配列 arr[] と、2つの整数 A および B が与えられます。この記事のゴールは、「A の出現回数」と「B の出現回数」が等しくなるような部分配列（サブ配列）の総数を求めることです。

例として、配列が [1, 2, 3]、A = 1、B = 2 である場合を考えてみましょう。このとき条件を満たす部分配列は [3]、[1, 2]、[1, 2, 3] となります。

入出力の例

例1

入力: arr[] = { 2, 2, 1, 1, 1, 5 }、A = 1、B = 5

出力: 条件を満たす部分配列の個数：4

説明: 該当する部分配列は [2]、[2]、[2, 2]、[1, 5] の4つです。最初の3つは 1 も 5 も含まないため出現回数が 0 回同士で等しく、最後の [1, 5] はどちらも 1 回ずつ含まれています。

例2

入力: arr[] = { 5, 3, 7, 5, 3 }、A = 1、B = 2

出力: 条件を満たす部分配列の個数：15

説明: この場合、1 と 2 が一度も登場しない（出現回数が 0 回同士で等しい）部分配列がすべて該当します。

[5], [3], [7], [5], [3] — 5個
[5,3], [3,7], [7,5], [5,3] — 4個
[5,3,7], [3,7,5], [7,5,3] — 3個
[5,3,7,5], [3,7,5,3] — 2個
[5,3,7,5,3] — 1個

合計 15 個の部分配列が条件を満たします。

アルゴリズムのアプローチ

最もシンプルな方法は、2重ループですべての部分配列を生成し、それぞれについて A と B の出現回数を比較することです。外側のループ変数 i を 0 から size−1 まで、内側のループ変数 j を i から size−1 まで動かすことで、arr[i] から arr[j] までのすべての部分配列を網羅的に調べられます。

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

• 関数 sub_EqualOccurrence(int arr[], int size, int A, int B) は配列と A・B の値を受け取り、条件を満たす部分配列の個数を返します。

• カウンター count を 0 で初期化します。

• i = 0 から size−1 までの外側のループの中で、total_A と total_B を 0 で初期化します。

• j = i から size−1 までの内側のループで、arr[j] が A なら total_A を、B なら total_B をインクリメントします。

• total_A と total_B が等しければ count を増やします（その部分配列には A と B が同数含まれています）。

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

なお、A と B がどちらも出現しない部分配列も、出現回数が 0 回同士で等しいため条件を満たす点に注意してください。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int sub_EqualOccurrence(int arr[], int size, int A, int B){
    int count = 0;
    for (int i = 0; i <= size - 1; i++){
        int total_A = 0;
        int total_B = 0;
        for (int j = i; j <= size - 1; j++){
            if (arr[j] == A){
                total_A++;
            }
            else if (arr[j] == B){
                total_B++;
            }
            if(total_A == total_B){
                count++;
            }
        }
    }
    return count;
}
// Driver code
int main(){
    int arr[] = { 2, 3, 1, 1, 4, 5 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int A = 1, B = 5;
    cout<<"Count of subarrays with equal number of occurrences of two given elements are: "<<sub_EqualOccurrence(arr, size, A, B);
    return (0);
}

実行結果

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

Count of subarrays with equal number of occurrences of two given elements are: 5

配列 { 2, 3, 1, 1, 4, 5 }、A = 1、B = 5 の場合、条件を満たす部分配列は 5 個あります。

計算量と改善のヒント

この方法の時間計算量は O(n²) です。すべての部分配列を漏れなく確認できる一方で、配列サイズが大きくなると処理時間が増加します。

より高速化したい場合は、累積和（プレフィックスサム）とハッシュマップを組み合わせた O(n) の手法が有効です。走査しながら「A の出現回数 − B の出現回数」の差分を記録し、同じ差分が過去に何回出現したかを集計することで、線形時間で答えを求められます。

まとめ

本記事では、C++ を使って「2つの指定された要素 A と B の出現回数が等しい部分配列」の個数を数える方法を解説しました。2重ループによる O(n²) のアプローチはロジックが分かりやすく、小〜中規模の配列に対しては十分実用的です。大規模データを扱う際は、プレフィックスサムとハッシュマップによる最適化も検討してみてください。