Leetcode[15]-3Sum

Leetcode[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:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
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)

分析：根據題意，我們可以要找出三個數相加等於0的這樣的一個集合，所以采用二維數組存儲。

首先抽取一個變量出來，該變量從左往右遞歸遍歷，遞歸的同時設置兩個變量，讓其一個從第一個變量的右邊，一個從數組的末端，同步的向中間遍歷，有點類似於快速排序的判斷方式，

依次遞歸，直到第一個變量條件終止為止。

Code(c++):

class Solution {
public:
    vector > threeSum(vector &nums) {
        vector >  result;

        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); i++){
            if(i > 0 && nums[i] == nums[i-1]) continue;
            threeNumber(nums, result, i); 
        }
        return result;
    }
    //return vector > results 
    void threeNumber(vector &nums, vector > &results, int curIndex) {
        int i = curIndex + 1;
        int j = nums.size()-1;

        while(i < j){
            if(nums[curIndex] + nums[i] + nums[j] < 0)   i++;
            else if(nums[curIndex] + nums[i] + nums[j] > 0)   j--;
            else{
                vector v;
                v.push_back(nums[curIndex]);
                v.push_back(nums[i]);
                v.push_back(nums[j]);
                results.push_back(v);
                i++; j--;
                while(i < j && nums[i]==nums[i - 1]) i++;
                while(j > i && nums[j] == nums[j + 1]) j--;
            }
        }
    }
};