C++で解く「Contains Duplicate III」問題：multisetを使った効率的な判定方法

整数型の配列が与えられ、配列内に異なる2つのインデックス i と j が存在するかどうかを判定する問題を考えます。条件は「nums[i] と nums[j] の絶対差が t 以下」かつ「i と j の絶対差が k 以下」であることです。例えば、入力が [1,2,3,1]、k = 3、t = 0 の場合、条件を満たすペアが存在するため true を返します。

解法アプローチ

この問題は、平衡二分探索木（C++では multiset）を利用することで効率的に解けます。手順は以下の通りです。

• 空の集合 s を用意し、n を nums 配列のサイズとします。
• i を 0 から n − 1 までループさせます。
  • x を「nums[i] 以上の値を持つ最小の要素」（lower_bound の結果）とします。
  • x が集合の末尾ではなく、その値が nums[i] + t 以下であれば true を返します。
  • x が集合の先頭要素でない場合は、次の処理を行います。
    • x を1つ前の要素へ移動します。
    • その値 + t が nums[i] 以上であれば true を返します。
  • nums[i] を s に挿入します。さらに i >= k の場合、範囲外となった nums[i − k] を s から削除します。
• ループ完了後に該当するペアが見つからなければ、false を返します。

計算量について

multiset の挿入・検索・削除の各操作は O(log k) で実行できるため、全体の時間計算量は O(n log k)、空間計算量は O(min(n, k)) となります。これにより、素朴な全ペア探索（O(n²)）よりも大幅に高速化できます。

C++での実装例

以下の実装コードを見ると、動作の理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset <int> s;
        int n = nums.size();
        for(int i = 0; i< n; i++){
            multiset <int> :: iterator x = s.lower_bound(nums[i]);
            if(x != s.end() && *x <= nums[i] + t ) return true;
            if(x != s.begin()){
                x = std::next(x, -1);
                if(*x + t >= nums[i])return true;
            }
            s.insert(nums[i]);
            if(i >= k){
                s.erase(s.lower_bound(nums[i - k]));
            }
        }
        return false;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,1};
    cout << (ob.containsNearbyAlmostDuplicate(v, 3,0));
}

入力

[1,2,3,1]
3
0

出力

1