与えられたint型配列から、合計した値が0になる3つの数値のパターンを全て探す問題です。
下記は時間計算量O(N^2 log N)の一例です。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::set<std::vector<int>> return_value;
for (size_t i = 0; i < nums.size()-2; i++) {
for (size_t j = i+1; j < nums.size()-1; j++) {
const int target = -(nums[i] + nums[j]);
if (target < nums[j+1] || nums.back() < target) {
continue;
}
auto it = std::lower_bound(nums.cbegin()+j+1, nums.cend(), target);
if (*it == target) {
return_value.insert({ nums[i], nums[j], target });
}
}
}
return std::vector<std::vector<int>>(return_value.cbegin(), return_value.cend());
}
};大まかには下記のことを行っています
- 昇順にソート ( O(N log N) )
- 末尾の要素を除き、2つの値の全てのペアを探す ( O(N^2) )
- 2. のペアに対して、合計が0になる値を2分探索を使用して値を探す ( O(log N) )
- 該当する値があれば、ユニークなコンテナ( std::set )に挿入する
- ユニークなコンテナを std::vector に変換して返却
従って時間計算量は 2. × 3. の O(N^2 log N) になります。
余談ですが、 std::set は２分木で実装されています。
Hash Set である std::unordered_set は使用できないか調べた結果、テンプレートパラメータ「Hash (= std::hash )」の実装にstd::vectorは存在しないため、自作のHash関数を指定する必要がありそうです。(参考: C++ unordered_set of vectors)
以上です！