15. 3 Sum

問題

找三個數加起來是0的，並且返回這些可能的數

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
    nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
    nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
    nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

Idea

Solution

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> results;
    sort(nums.begin(), nums.end());
    set<vector<int>> set;

    for(int i=0; i<nums.size(); i++){

        int start = i+1;
        int end = nums.size()-1;

        while(start < end){
            int sum = nums[i] + nums[start] + nums[end];
            if( sum == 0){
                set.insert({nums[i], nums[start], nums[end]});
                start++;
                end--;
            }else if(sum < 0){
                start++;
            }else{
                end--;
            }
        }
    }

    for(auto list: set){
        results.push_back(list);
    }

    return results;
}