Petty C++ - アルゴリズムの微調整 - 三つの数の合計

課題の説明#

整数配列 nums が与えられた場合、i != j、i != k、j != k を満たし、nums [i] + nums [j] + nums [k] == 0 を満たす三つ組 [nums [i]、nums [j]、nums [k]] が存在するかどうかを判断します。0 に等しい和で重複しないすべての三つ組を返します。
注意：答えには重複する三つ組を含めることはできません。

解決策#

二重ポインタを使用します。具体的には、三つの数字の関係を考慮する必要があるため、数字を固定するたびに二重ポインタを使用して一度走査します。

走査中に、現在の合計結果に基づいて二重ポインタの位置を調整する必要があります。ここで、ソートが使用されます。

実装#

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); ++i){
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int p = i+1;
            int q = nums.size()-1;
            while(p < q){
                int sum = nums[i] + nums[p] + nums[q];
                if(sum == 0){
                    res.push_back({nums[i], nums[p], nums[q]});
                    while(p<q && nums[p] == nums[p+1]) p++;
                    while(p<q && nums[q] == nums[q-1]) q--;
                    p++;
                    q--;
                }
                if(sum > 0) q--;
                if(sum < 0) p++;
            }
        }
        return res;
    }
};

コードの圧縮などの行動を考慮しない場合、以下の詳細な調整ができます。

調整#

一時オブジェクトの作成を減らす#

emplace_back を使用すると、結果のベクターに要素を追加する際に一時オブジェクトの作成を減らすことができます。
res.emplace_back(std::initializer_list<int>{nums[i], nums[p], nums[q]});

計算量のキャッシュ#

アクセス効率を向上させるために、配列のサイズを事前にキャッシュします。
const int n = nums.size()

境界の詳細#

少なくとも三つの数字を保存する必要があるため、ループの境界を調整できます：
for(int i =0; i < n - 2; ++i)