C++で解く「重複の検出 II」（Contains Duplicate II）の解法と実装例

問題概要

配列と整数 k が与えられます。このとき、配列の中に異なる 2 つのインデックス i と j が存在し、nums[i] = nums[j] かつ i と j の絶対差が k 以下となるかどうかを判定するのが本問題です。

たとえば、入力が [1,2,4,1]、k = 3 の場合を考えてみましょう。インデックス 0 と 3 の要素はどちらも 1 であり、そのインデックスの差は 3 なので、出力は True になります。

解法のアプローチ

この問題は、次の手順に従って解くことができます。

• (値, インデックス) のペアを格納する配列 nn を定義します。
• i を 0 から nums のサイズまで 1 ずつ増やしながら、{nums[i], i} を nn の末尾に挿入していきます。
• 配列 nn をソートします。ソートにより、同じ値どうしが必ず隣接して並びます。
• i を 1 から nn のサイズまで 1 ずつ増やしながら、nn[i] の値が nn[i-1] の値と一致し、かつ両者のインデックスの絶対差が k 以下であれば true を返します。
• すべてのペアを調べても条件を満たすものが見つからなければ、false を返します。

この手法のポイント

ソート後は同一の値が必ず隣接するため、隣り合う要素同士だけを比較すればよいのがこのアプローチの強みです。全体の計算量は O(n log n) となり、効率的に判定できる点も魅力です。

実装例

理解を深めるために、以下の C++ 実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool containsNearbyDuplicate(vector<int>& nums, int k) {
      vector<pair<int, int>> nn;
      for (int i = 0; i < nums.size(); i++) {
         nn.push_back(make_pair(nums[i], i));
      }
      sort(nn.begin(), nn.end());
      for (int i = 1; i < nn.size(); i++) {
         if (nn[i].first == nn[i - 1].first && abs(nn[i].second - nn[i - 1].second) <= k)
            return true;
      }
      return false;
   }
};
int main(){
   Solution ob;
   vector<int> v = {1,2,4,1};
   cout << (ob.containsNearbyDuplicate(v, 3));
}

入力

{1,2,4,1}

出力

1

出力は 1（true）となり、値が等しくインデックスの差が k 以内にある 2 つの要素が存在することが確認できました。