[LeetCode July Challange]Day8-3Sum

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

time complexity : O(n^2)
space complexity : O(n^2)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        int size = nums.size();
        
        for (int i=0; i<size-2; ++i) {
            // 3sum can't be = 0
            if (nums[i] > 0) break;

            // repeat handle
            if (i>0 && nums[i]==nums[i-1]) continue;

            // 2-pointer
            int l = i+1;
            int r = size-1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.push_back({nums[i], nums[l++], nums[r--]});

                    // repeat handle
                    while (l<r && nums[l] == nums[l-1]) ++l;
                    while (l<r && nums[r] == nums[r+1]) --r;
                } else if (sum > 0) 
                    --r;
                else
                    ++l;
            }
        }
        
        return res;
    }
};

用暴力法，O(n^3)的時間，會發生Time Limit Exceeded。
題目答案需要「不重覆」的pair，將題目sort後(O(nlogn))，一個一個用2-pointer的方式(O(n^2))，跳過重覆的部份，來得到最後的結果。