Matrix

Problem Description#

Given an integer array nums, determine whether there exists a triplet [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Please return all unique triplets that sum to 0.
Note: The answer cannot contain duplicate triplets.

Solution Approach#

Use two pointers. Specifically, because we need to consider the relationship between three numbers, for each fixed number, we traverse using two pointers.

During the traversal process, we need to adjust the positions of the two pointers based on the current sum. This requires sorting.

Implementation#

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;
    }
};

Without considering code compression and other behaviors, further adjustments can be made in the following aspects:

Adjustments#

Reduce the creation of temporary objects#

Using emplace_back can reduce the creation of temporary objects when adding elements to the result vector.
res.emplace_back(std::initializer_list<int>{nums[i], nums[p], nums[q]});

Cache calculations#

Caching the size of the array in advance improves access efficiency.
const int n = nums.size()

Boundary details#

Because at least three numbers need to be saved, the loop boundary can be adjusted:
for(int i =0; i < n - 2; ++i)