I posted this on Stackoverflow but found out that it would be better to post it here. I am sorry if I mess something up with regards to formatting or other issues, bear with me.

I have recently started to work through the problems on Leetcode, for the sake of bettering my own skills as well as preparing for interviews. I was faced with the 3Sum problem which is:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Now I thought about this, the brute force solution is to iterate through the array twice for every number to find the other two numbers that make the sum of the three equal 0. This would have a time complexity of O(n^3) which is less than ideal. So I thought maybe it would be instead good to store all the pairs in the given array.

Then iterate through the array and see if the sum with any pair is equal to 0, and push the pair along with that number into a vector for the output. It is slightly working backwards, and I thought that this would give me an efficiency of O(n^2)

My code is this:

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<pair<int,int>> pairs;
    vector<vector<int>> output;
    
    if(nums.size()<3){
        return output;
    }
    
    for(int i=0; i<nums.size();i++){
        for(int j=i+1; j<nums.size();j++){
            
                pairs.push_back(make_pair(nums.at(i),nums.at(j)));
            
            
        }
    }
    
    sort(pairs.begin(),pairs.end());
    pairs.erase(unique(pairs.begin(),pairs.end()),pairs.end());
    
    for(int i=0; i<nums.size();i++){
        for(auto x:pairs){
            if(x.first!=nums.at(i) && x.second!=nums.at(i)){
                if(x.first+x.second+nums.at(i)==0){
                    vector<int> curr;
                    curr.push_back(x.first);
                    curr.push_back(x.second);
                    curr.push_back(nums.at(i));
                    sort(curr.begin(),curr.end());
                    output.push_back(curr);
                       
                    
                }
            }
            
        }
    }
    int count = 0;
    for(int i:nums){
        if(i==0){
            count++;
            if(count==3){
                vector<int> zeros;
                zeros.push_back(0);
                zeros.push_back(0);
                zeros.push_back(0);
                output.push_back(zeros);
                break;
            }
        }
    }
    
    sort(output.begin(),output.end());
    output.erase(unique(output.begin(),output.end()),output.end());
    return output;
    
}

At the end in the lines:

    int count = 0;
    for(int i:nums){
        if(i==0){
            count++;
            if(count==3){
                vector<int> zeros;
                zeros.push_back(0);
                zeros.push_back(0);
                zeros.push_back(0);
                output.push_back(zeros);
                break;
            }
        }
    }

Here I am checking if there are 3 or more zeros in the given input and then pushing a vector [0,0,0] into the output to cover that case, because my condition for avoiding duplicates in the line below avoids zeros (something I haven't been able to figure out):

 if(x.first!=nums.at(i) && x.second!=nums.at(i)){

So after running it, the Leetcode test cases with very large inputs give me a Time Limit Exceeded message, I am wondering what am I doing wrong or how I can go about to make it better? I was thinking maybe the sorting is an issue but from what I know O(n^2) should be dominant compared to O(nlogn).

Thank you very much in advance, I appreciate any and all assistance! Apologies if my code is "noobish" I am still learning and trying to improve and get better.