LeetCode15: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)

這道題可以用求兩個數的和相同的解法來求解。需要注意的是對重復元素的處理，如果不加上這個減枝處理，在leetcode中會顯示超時。
首先對數組進行排序，時間復雜度是O(Nlog(N))。
然後定義三個指針，第一個指針從頭遍歷到尾，第二個指針和第三個指針和求兩個數的和時的那兩個指針一樣從兩端開始遍歷，左端由第一個指針來確定。這樣時間復雜度是O(N^2)。總的時間復雜度是O(N^2)。一定要加上對重復元素的減枝處理。

runtime:68ms

class Solution {
public:
    vector> threeSum(vector& nums) {
        int length=nums.size();
        vector> result;
        if(length<3)
            return result;

        sort(nums.begin(),nums.end());
        auto iter1=nums.begin();
        for(;iter1!=nums.end()-2;iter1++)
        {
            auto iter2=iter1+1;
            auto iter3=nums.end()-1;
            while(iter2 tmp;
                    tmp.push_back(*iter1);
                    tmp.push_back(*iter2);
                    tmp.push_back(*iter3);
                    result.push_back(tmp);
                    while(*iter2==*(iter2+1)&&(iter2+1)