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

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
	[-1, 0, 1],
	[-1, -1, 2]
]

Solution in C++

class Solution {
public:
    
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int>n(3);
        set<vector<int>> sRet;
        vector<vector<int>> vRet;

        sort(nums.begin(), nums.end());

        map<int,int> mNums;
        for(int i=0; i<nums.size(); i++) mNums[nums[i]]=i+1;

        for(int i=0;i<nums.size(); i++) {
            if (nums[i]>0) break;
            n[0]=nums[i];
            
            for(int j=i+1;j<nums.size(); j++) {
                int sum2=0-nums[i]-nums[j];
                if (sum2<nums[j]) break;
                n[1]=nums[j];
                if (mNums[sum2] && mNums[sum2]!=(i+1) && mNums[sum2]!=(j+1)) {
                    n[2]=sum2;
                    sRet.insert(n);
                }
            }
        } 
        
        for(auto s:sRet) vRet.push_back(s);
        
        return vRet;
    }
};
  • No labels