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

解題思路:

    在上一篇博客裡面，簡述了Two Sum的做法，而這道題目與其類似，我們可以通過把等式 a + b + c = 0 轉換

成求 -b = a + c ,關於這裡為什麼是選擇b做和？因為我們最終所要求的三元組裡面是非降序的，而選擇b做和的

一個好處就是我們只用去枚舉b的位置.假設數組長度為n,則b的可能位置為[1,n-2].這題目裡面個人感覺主要是怎

麼去重的問題,下面闡釋下我的做法:當枚舉b時，由於我們設定頭尾遍歷法求解，那麼滿足條件的三元組且

重復的必然相鄰(因為b此時是定值),所以我們需要記錄上一次找到的滿足條件的三元組，然後做個比較即可去重.

這裡還存在一個優化:現假設我們枚舉b的位置為k，如果k - 1的位置的數值也等於b，則滿足等式a + b + c = 0 

且的結果集我們已經在k - 1時已經得知，所以我們這裡只需要去找尋有沒有滿足這樣的等式即

可.最終所要找尋到的結果集就是無重復的結果集.

下面是解題代碼:

class Solution 
{
public:
    vector > threeSum(vector &num) 
    {
        sort(num.begin(),num.end());
        int n = num.size();
        vector > res;
        int arr[3] = {-1,-1,-1};
        for(int k = 1 ; k < n - 1 ;++k)
        {
            if(k > 1 && num[k] == num[k-1])
            {
                long long key = -num[k] * 2 ;
                if(num[k-1] != num[k-2] && binary_search(num.begin()+k+1,num.end(),key))
                {
                    arr[0] = num[k] , arr[1] = num[k] , arr[2] = key;
                    res.push_back(vector(arr,arr+3));
                }
                continue;
            }
            int sum = -num[k],i=0,j=n-1;
            while(i < k && j > k)
            {
                long long tmp = num[i] + num[j] ;
                if(tmp == sum)
                {
                    if(num[i]!=arr[0] || num[k]!=arr[1] || num[j]!=arr[2])
                    {    
                        arr[0] = num[i] , arr[1] = num[k] , arr[2] = num[j];
                        res.push_back(vector(arr,arr+3));
                    }
                    ++i,--j;
                    continue;
                }
                tmp > sum ? --j : ++i ;
            }
        }
        return res;
    }
};