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