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, since we need to consider the relationship between three numbers, we iterate through the array while fixing one number.

During the iteration, we need to adjust the positions of the two pointers based on the current sum. Sorting is used here.

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

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

Adjustments#

Reduce the creation of temporary objects#

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

Cache calculations#

Cache the size of the array in advance to improve access efficiency.
const int n = nums.size()

Boundary details#

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