C++で配列内にk距離以内の重複要素が存在するかどうかを判定する方法

本記事では、ソートされていない配列の中に、互いにk距離（インデックス差）以内にある重複した要素が存在するかどうかを判定する方法を解説します。

例えば、要素のリストが {1, 2, 3, 1, 4, 5} であり、k = 3 の場合を考えてみましょう。このとき、2つの「1」の間隔は3であるため、プログラムは true を返します。一方、k = 2 であれば、重複は検出されず false となります。

アルゴリズムの考え方：ハッシュテーブル（セット）を活用

この問題は、ハッシュテーブル（ここでは C++ の set）を使うことで効率的に解決できます。手順は以下の通りです。

• 空のハッシュテーブル（セット）を作成する
• 各インデックス i について、要素 e = arr[i] に対して以下を繰り返す
  • e がすでにセットに存在すれば true を返す（k距離以内の重複が見つかった）
  • 存在しなければ e をセットに追加し、i >= k の場合は (i-k) 番目の要素をセットから削除する（ウィンドウ範囲外の要素を除外）

この方法では、常に直近の k 個の要素だけをセットに保持することになるため、時間計算量は O(n)、空間計算量は O(k) で処理できます。

C++による実装例

#include<iostream>
#include<set>
using namespace std;

bool hasDuplicateWithDistK(int arr[], int n, int k) {
   set<int> element_set;
   for (int i = 0; i < n; i++) {
      // すでにセット内に同じ要素があれば、k距離以内の重複とみなせる
      if (element_set.find(arr[i]) != element_set.end())
         return true;
      element_set.insert(arr[i]);
      // ウィンドウサイズを維持するため、(i-k)番目の要素を削除
      if (i >= k)
         element_set.erase(arr[i-k]);
   }
   return false;
}

int main () {
   int arr[] = {10, 5, 3, 4, 3, 5, 6};
   int n = sizeof(arr) / sizeof(arr[0]);
   if (hasDuplicateWithDistK(arr, n, 3))
      cout << "Duplicate element has found";
   else
      cout << "Duplicate element has not found";
}

実行結果

Duplicate element has found

上記の例では、配列 {10, 5, 3, 4, 3, 5, 6} に対して k = 3 で判定しています。「3」がインデックス2と4に出現しており、その間隔は2（k = 3 以内）であるため、「重複要素が見つかった」という結果が出力されます。

まとめ

スライディングウィンドウの考え方とハッシュセットを組み合わせることで、配列内の k 距離以内の重複要素を線形時間で効率的に検出できます。要素の挿入・検索・削除が平均 O(log n)（set の場合）または O(1)（unordered_set の場合）で行えるため、大規模なデータにも対応可能です。