C++で元の配列と同じ異なる要素数を持つ部分配列を数える方法

整数を含む配列 arr[] が与えられたとき、各部分配列に含まれる「異なる要素の種類数」が、元の配列全体の異なる要素の種類数と一致するような部分配列をすべて数えるのが本記事の目的です。

例えば、元の配列が [1,1,2,3] の場合、条件を満たす部分配列は [1,2,3] と [1,1,2,3] の2つになります。元の配列の異なる要素数は3であり、これらの部分配列の異なる要素数もそれぞれ3だからです。

それでは、具体的な例で確認してみましょう。

入力例と出力例

例1

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

出力 − 元の配列と同じ異なる要素数を持つ部分配列の数:6

説明 − arr[] の異なる要素は4つ(1、2、3、4)です。左から右へ異なる要素を数えると、条件を満たす部分配列は以下の6つになります。

[1,2,1,2,3,4]
[2,1,2,3,4]
[1,2,3,4]
[1,2,3,4,2]
[2,1,2,3,4,2]
[1,2,1,2,3,4,2]

例2

入力 − arr[] = {8,7,5,6,10}

出力 − 元の配列と同じ異なる要素数を持つ部分配列の数:1

説明 − arr[] の異なる要素は5つ(5、6、7、8、10)です。同じ異なる要素数を持つ部分配列は配列全体 [8,7,5,6,10] のみで、該当数は1となります。

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

この問題は、スライディングウィンドウ(尺取り法)とハッシュマップ(unordered_map)を組み合わせることで効率的に解けます。手順は以下の通りです。

• 整数型の配列 arr[] を受け取り、配列のサイズを計算します。

• 関数 sub_distinct(int arr[], int size) は配列を受け取り、元の配列と同じ異なる要素数を持つ部分配列の個数を返します。

• カウント用の一時変数 count と、ウィンドウの両端を表す変数 right および left を用意します。

• 要素の出現回数を管理するため、unordered_map 型の変数 um を宣言します。

• まず 0 から配列サイズまでの FOR ループで、arr[i] をキーとして um に登録します。

• um のサイズ(=元の配列の異なる要素数)を取得した後、um をクリアします。

• 再び 0 から配列サイズまでの FOR ループを開始します。

• ループ内では、right < 配列サイズ かつ left < um のサイズである限り WHILE ループを回し続けます。

• WHILE ループ内では um[arr[right]] をインクリメントし、その値が 1 になった場合(新しい異なる要素が出現した場合)は left をインクリメントします。

• WHILE ループを抜けたら right をインクリメントします。

• left == um のサイズ(=ウィンドウ内に全ての異なる要素が揃った状態)であれば、count に size - right + 1 を加算します。

• その後、um[arr[i]] をデクリメントし、値が 0 になったら left をデクリメントしてウィンドウを縮めます。

• 最後に count を返します。

• main 関数で結果を出力します。

コード例

#include <bits/stdc++.h>
using namespace std;
int sub_distinct(int arr[], int size){
   int count = 0, right = 0, left = 0;
   unordered_map<int, int> um;
   for (int i = 0; i < size; ++i){
      um[arr[i]] = 1;
   }
   int um_size = um.size();
   um.clear();
   for(int i = 0; i < size; ++i){
      while (right < size && left < um_size){
         ++um[arr[right]];
         if (um[arr[right]] == 1){
            ++left;
         }
         ++right;
      }
      if (left == um_size){
         count = count + (size - right + 1);
      }
      --um[arr[i]];
      if (um[arr[i]] == 0){
         --left;
      }
   }
   return count;
}
int main(){
   int arr[] = {4, 3, 2, 5};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subarrays having total distinct elements same as original array are: "<<sub_distinct(arr, size);
   return 0;
}

実行結果

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

Count of subarrays having total distinct elements same as original array are: 1

このアルゴリズムの計算量は O(n) です。各要素が高々2回(ウィンドウの拡大時と縮小時)しか処理されないため、全ての部分配列を素朴に調べる O(n²) の方法よりも大幅に高速に動作します。