小氣的C++ - 算法調精 - 三數之和

题目描述#

給你一個整數數組 nums ，判斷是否存在三元組 [nums [i], nums [j], nums [k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums [i] + nums [j] + nums [k] == 0 。請你返回所有和為 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 可以在向結果 vector 中添加元素時減少一次臨時對象的創建
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)