[LeetCode][Medium] 15. 3Sum

Leetcode 網址: https://leetcode.com/problems/3sum/

題目說明:

給定 n 個整數，triplets 定義為 3 個整數 a, b, c 能夠使得 a + b + c = 0，

請找出所有唯一的 triplets。

Note: [a, b, c] 與 [a, c, b] 視為同一組 triplets

解題說明:

首先我們將問題縮小，如果給定一個數字 a 要如何找出另外二個整數 b, c 使得 a + b + c = 0 呢?

直覺想法是暴力法，也就是枚舉剩下的數字，那麼其時間複雜度為 O (n * n) 

接著進一步研究發現，如果給定的是已經排序的數字，那麼我們找出 b, c 的時間複雜度只要 O(n)，

時間複雜度只要 O(n) 的原因是數字已經排序過，所以我們可以利用 two pointer 去逼近答案，

有了以上想法之後就可以實現算法了，最終的解法其時間複雜度為: O(n log n) + O(n * n) = O(n * n)。

程式碼

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<int> answer(3);
        vector<vector<int>> answers;
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.size() - 1;
            answer[0] = nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right] + nums[i];

                if (sum == 0) {
                    answer[1] = nums[left], answer[2] = nums[right];
                    if (answers.size() == 0 || answers[answers.size() - 1] != answer)  answers.push_back(answer); 
                    left++, right--;
                }
                else if (sum < 0) left++;
                else right--;
                
            }
        }
        
        return answers;
    }
};

結果

Runtime: 64 ms, faster than 91.33% of C++ online submissions for 3Sum.

Memory Usage: 20 MB, less than 89.41% of C++ online submissions for 3Sum.