57. 3Sum

Code(Language:C++) (Judger:cloudjudge-cluster-7)

class Solution {
public:
    /**
     * @param numbers: Give an array numbers of n integer
     * @return: Find all unique triplets in the array which gives the sum of zero.
     */
    vector<vector<int>> threeSum(vector<int> &numbers) {
        // write your code here
        vector<vector<int>> res; 
        const int size = numbers.size();
        if(size < 3){
            return res; 
        }
        sort(numbers.begin(), numbers.end()); 
        for(int i = 0; i <= size - 3; i++){
            if(i > 0 && numbers[i] == numbers[i - 1]){
                continue; 
            }
            int target = 0 - numbers[i]; 
            int left = i + 1; 
            int right = size - 1; 
            while(left < right){
                if(left > i + 1 && numbers[left] == numbers[left - 1]){
                    left++; 
                    continue;
                }
                int sum = numbers[left] + numbers[right]; 
                if(sum == target){
                    res.push_back({numbers[i], numbers[left], numbers[right]}); 
                    left++;
                    right--; 
                }
                else if(sum < target){
                    left++; 
                }
                else{
                    right--; 
                }
            }
        }
        return res; 
    }
};