【C++】指定サイズの部分配列に含まれる一意な整数の最大数を求める方法

問題の概要

この問題では、サイズnの配列と数値Mが与えられます。求めるのは、指定されたサイズの部分配列（サブ配列）に含まれる一意な整数の最大数を見つけるプログラムです。

つまり、重複のない要素（ユニークな要素）の数が最大となる、サイズMの部分配列を探す必要があります。

具体例で問題を理解する

入力 − array = {4, 1, 2, 1, 4, 3}、M = 4

出力 − 4

解説 − サイズ4の部分配列は以下の3通りが考えられます。

サイズ4の部分配列のすべての組み合わせ
{4, 1, 2, 1} = 一意な要素は3個
{1, 2, 1, 4} = 一意な要素は3個
{2, 1, 4, 3} = 一意な要素は4個

この中で一意な要素の数が最も多いのは {2, 1, 4, 3} の4個なので、答えは4となります。

解き方① 全探索（ブルートフォース）

最も単純なアプローチは、サイズMのすべての部分配列を生成し、それぞれに含まれる一意な要素の数を数え、これまでの最大値より大きければ記録を更新していく方法です。しかし、この方法はすべての部分配列を毎回走査するため計算コストが高く、効率が良くありません。

解き方② スライディングウィンドウ＋ハッシュマップ

より効率的なのがスライディングウィンドウ（滑動窓）テクニックです。サイズMのウィンドウを配列上で少しずつずらしながら、ハッシュテーブルで現在のウィンドウ内の一意な要素を管理することで、効率よく答えを求められます。

ウィンドウの操作手順は以下のとおりです。

• サイズMのウィンドウを作成し、含まれる要素をハッシュマップに格納します。
• ウィンドウを1つ右へずらし、新しく入ってくる要素をハッシュマップに追加するとともに、前のウィンドウから外れた要素を削除します。

例で見る処理の流れ

配列 = {4, 1, 2, 1, 4, 3}、ウィンドウサイズ M = 4 の場合の動きを表にまとめます。

この表から、ウィンドウがスライドするたびにハッシュマップが更新され、一意な要素の数が効率的にカウントされている様子がわかります。

C++での実装例

指定されたサイズの部分配列に含まれる一意な整数の最大数を求めるプログラムは以下のとおりです。

#include<bits/stdc++.h>
using namespace std;
int maxUniqueElement(int a[],int N,int M){
    map<int,int> hashMap;
    int uniqueCountWindow=0;
    int uniqueCount=0;
    for(int i=0;i<M;i++) {
        if(hashMap.find(a[i])==hashMap.end()) {
            hashMap.insert(make_pair(a[i],1));
            uniqueCountWindow++;
        }
        else
            hashMap[a[i]]++;
        }
        uniqueCount = uniqueCountWindow;
        for(int i=M;i<N;i++) {
            if(hashMap[a[i-M]]==1) {
                hashMap.erase(a[i-M]);
                uniqueCountWindow--;
            }
            else
                hashMap[a[i-M]]--;
                if(hashMap.find(a[i])==hashMap.end()){
                    hashMap.insert(make_pair(a[i],1));
                    uniqueCountWindow++;
                }
                else
                    hashMap[a[i]]++;
                    uniqueCount=max(uniqueCount,uniqueCountWindow);
            }
        return uniqueCount;
}
int main(){
    int arr[] = {4, 1 ,2, 1, 4, 3};
    int M=4;
    int N=sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum number of unique elements in sub-array of size "<<M<<" is "<<maxUniqueElement(arr,N,M)<<endl;
}

出力

The maximum number of unique elements in sub-array of size 4 is 4

計算量について

この解法では、各要素はウィンドウへの追加と削除をそれぞれ1回ずつ行うだけです。std::mapを使用した場合、1回の操作はO(log M)となるため、全体の計算量はO(N log M)です。std::unordered_mapを使えば、平均O(N)まで高速化できます。全探索のO(N×M)と比べると、大きな配列でも実用的な速度で動作するのがポイントです。