15. 3Sum

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.
Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

呼，這題花了很多的時間寫。大約用了兩週的時間。雖然不是全部時間都在寫

其實這題就是Two Sum 的衍生，但是答案不只有一組所以你必須將所有的組合通通記錄下來

我本來的解法

class Solution {
public:
    vector<vector<int>> reallyanswer;
    set<vector<int>> answer;
    unordered_map<int, int> twoSumMap;

    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        if (nums.size() < 3)
        {
            return {};
        }
        
        sort(nums.begin(), nums.end());        
        
        
        for (int i = 0; i < nums.size() - 2; i++)
        {           
            twoSumMap.clear();
            
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }

            for (int j = i + 1; j < nums.size(); j++)
            {
                if (twoSumMap.count(-nums[i] - nums[j]) > 0)
                {
                    answer.insert({ nums[i], nums[twoSumMap[-nums[i] - nums[j]]], nums[j] });
                }
                else
                {
                    twoSumMap[nums[j]] = j;
                }
            }
        }

        for (auto v : answer)
        {
            reallyanswer.push_back(move(v));
        }

        return reallyanswer;
    }
};

 

   上面的寫法問題在於你會重複很多次找到相同的組合，雖然你是用map紀錄，最後再放到vector中。

但是時間就比人家慢非常多。

後來看到人家的解法如下

class Solution {
public:
 vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> triples;
    sort(nums.begin(), nums.end());
    int i = 0, last = nums.size() - 1;
    while (i < last) {
        int a = nums[i], j = i+1, k = last;
        
        //開始two sum的邏輯
        while (j < k) {
            //有點雙指標的寫法 從頭尾一路逼近中間
            int b = nums[j], c = nums[k], sum = a+b+c;

            //這個組合符合所以加入
            if (sum == 0) triples.push_back({a, b, c});
            //後面的while loop是因為要過濾掉重複的b
            if (sum <= 0) while (nums[j] == b && j < k) j++;
            //後面的while loop是因為要過濾掉重複的c
            if (sum >= 0) while (nums[k] == c && j < k) k--;
        }
        //while loop是因為要略過重複的a
        while (nums[i] == a && i < last) i++;
    }
    return triples;
}       
};