【LeetCode】 15. 3Sum

Description

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.

給一包含n個整數的陣列nums，有任意三個元素a, b, c能夠使a + b + c = 0 成立嗎？找到所有陣列中的三個數，相加總和為零。
提示：答案中不可有重複的組合。

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

• 請先看完1. Two Sum。
• 這題變為三個數字總和為零，那只要用loop將其中一個數字設為目標數跑過一輪即可。
• 為了加速，將數列先排列，然後根據總和太大或太小往中間慢慢靠近。
• 為了排除重複的組合，答案換為set再換回去(感覺有更好的做法，這樣做好像有點慢)。

Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        vector<vector<int>> ans;
        
        if (nums.empty())
            return ans;
        
        sort(nums.begin(),nums.end());
        unordered_set<int> seen;
        
        int s = nums.size();
        for (int i = 0; i < s - 2; i++)
        {
            if (seen.find(nums[i]) != seen.end())
                continue;
            
            int target = -nums[i];
            int b = i + 1, e = s - 1;
            while (b < e)
            {
                if (nums[b] + nums[e] == target)
                {
                    ans.push_back({nums[b], nums[i], nums[e]});
                    b++;
                    e--;
                }
                else if (nums[b] + nums[e] > target)
                    e--;   
                else
                    b++;
            }
            seen.insert(nums[i]);
        }
        set<vector<int>> u(ans.begin(),ans.end());
        ans.assign(u.begin(),u.end());
        return ans;
    }
};

tags: LeetCode C++