C++で重複要素を含まない部分配列から形成されるペアの数を数える方法

問題の概要

整数要素を含む配列 arr[] が与えられたとき、各部分配列がすべて異なる（重複しない）要素のみを持つという条件のもとで、その部分配列の要素から形成できるペアの総数を求めるのが目標です。

例えば、配列が [1, 2, 2, 3, 3] の場合、重複を含まない部分配列は [1, 2] と [2, 3] になります。これらから形成されるペアは (1, 2) と (2, 3) なので、ペアの総数は 2 となります。

入出力例で理解する

例 1

入力： arr[] = {1, 2, 5, 3}

出力： 重複要素なしの部分配列から形成されるペアの数：6

説明： すべて異なる要素を持つ部分配列は [1, 2, 5, 3] であり、可能なペアは (1,2)、(1,3)、(1,5)、(2,5)、(2,3)、(5,3) の 6 組です。

例 2

入力： arr[] = {1, 2, 1, 2, 3}

出力： 重複要素なしの部分配列から形成されるペアの数：5

説明： すべて異なる要素を持つ部分配列と、そこから得られるペアは以下の通りです。

[1,2]   → ペア: (1,2)
[2,1]   → ペア: (2,1)
[1,2,3] → ペア: (1,2), (2,3), (1,3)
合計ペア数: 5

アルゴリズムの考え方（スライディングウィンドウ）

この問題はスライディングウィンドウ（二重ポインタ）のテクニックを使うことで効率的に解けます。ウィンドウを右端から拡大しながら重複がない状態を保ち、新しい要素を追加するたびに「既存のウィンドウ内要素との組み合わせ」をカウントに加算していきます。重複が見つかった場合は、ウィンドウの左端を縮めて重複を取り除きます。

以下のプログラムで使用している手順は次の通りです。

• 整数型の配列を入力として受け取ります。
• 関数 distinct_pairs(int arr[], int size) は配列を受け取り、重複要素なしの部分配列から形成されるペアの数を返します。
• カウントの初期値を 0 とし、変数 start = end = 0 を用意します。
• ウィンドウ内の要素を記録するためのフラグ配列 vector<bool> check(size, false) を作成します。
• start が size 未満である間、外側の WHILE ループを回します。
• ループ内では、start < size かつ check[arr[start]] が false である間、内側の WHILE ループを実行し、count += (start - end) としてペア数を加算、check[arr[start]] を true に設定し、start を 1 増やします。
• 続いて、end < start、start != size、かつ check[arr[start]] が true である間、WHILE ループを実行し、check[arr[end]] を false に戻して end を 1 増やします（重複が検出された位置までウィンドウの左端を縮めます）。
• 最後にカウントを返します。
• 結果を出力します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
    int count = 0;
    int start = 0;
    int end = 0;
    vector<bool> check(size, false);
    while (start < size){
        while (start < size && !check[arr[start]]){
            count += (start - end);
            check[arr[start]] = true;
            start++;
        }
        while (end < start && (start != size && check[arr[start]])){
            check[arr[end]] = false;
            end++;
        }
    }
    return count;
}
int main(){
    int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
    return 0;
}

実行結果

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

Count of pairs formed by distinct element sub-arrays are: 17

まとめ

このアルゴリズムは各要素を高々 2 回しか走査しないため、時間計算量は O(n)、追加で必要なメモリは O(n)（フラグ配列分）です。すべての部分配列を実際に生成して調べる O(n²) の素朴なアプローチと比べ、大きな配列でも高速に動作する点が大きな魅力です。スライディングウィンドウの考え方は、「連続する区間の中で条件を満たす範囲」を扱う多くの配列問題に応用できるので、ぜひ覚えておきましょう。