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

課題の説明#

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

解決方法#

双方向ポインタを使用します。具体的には、3 つの数字の関係を考慮する必要があるため、1 つの数字を固定するたびに、双方向ポインタを使用して 1 回走査します。

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

実装#

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()

境界の詳細#

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