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.
找出數組中三個元素和為0的序列集合。

分析：

 思路：
 1、由於是找出和為0的元素，首先對vector進行排序，有利於進一步處理。
 2、三個數字和首先想到的是固定一個數值，另兩個數字作為游標遍歷vector。例如：[-1, 0, 1, 2, -1, -4]中，排序後為[ -4, -1, -1, 0, 1, 2] 固定最小的首個數字為k1=-4，令k2從 -1 向右移動，k3 = 2向左移動。直至 k3游標移到k2游標位置，
 3、根據k2 + k3 + k1 ? 0 的關係，來決定游標移動方向，k1固定，當k2 + k3 + k1 > 0時，k3 左移（減小三個數和），反之k2右移。當相等時，存入數組，並令k2 k3同時移動，便面出現多組重覆集合的情況。

代碼：

vector<vector<int>> threeSum(vector<int>& vecNum) {
    vector<vector<int> > vecRes;
    if (vecNum.size() < 3)
    {
        return vecRes;
    }

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

    for (vector<int>::iterator iterBg = vecNum.begin(); iterBg < vecNum.end() - 2; iterBg++)
    {
        if (iterBg > vecNum.begin() && *(iterBg - 1) == *iterBg)
        {
            continue;
        }

        vector<int>::iterator iterL = iterBg + 1;
        vector<int>::iterator iterR = vecNum.end() - 1;

        while(iterL < iterR)
        {
            if (0 > *iterBg + *iterL + *iterR)
            {
                iterL++;
                while (*iterL == *(iterL - 1) && iterL < iterR)
                {
                    iterL++;
                }
            }
            else if (0 < *iterBg + *iterL + *iterR)
            {
                iterR--;
                while (*iterR == *(iterR + 1) && iterL < iterR)
                {
                    iterR--;
                }
            }
            else
            {
                vecRes.push_back({ *iterBg, *iterL, *iterR });
                iterL++;
                iterR--;
                while (*iterL == *(iterL - 1) && *iterR == *(iterR + 1) && iterL < iterR)
                {
                    iterL++;
                }
            }
        }
    }
    return vecRes;
}

備註：
感覺使用夾逼法，效率低而且思路也不開闊，後續會進行其他方法的研究，求大家多多指教。