leetcode-15 3Sum

題意: 給定一串數列,求出是否存在三數相加為零,若存在,輸出三數,注意每組三數不可重複


解題思路:這題是鼎鼎有名的3 sum problem, 在計算幾何學常用,其算法為對數列進行排序,針對每個數字做考慮,舉例來說,有一數列:
-7,-5,-3,-1,4,6,8,10
第一輪先考慮-7,使用兩個指標,start 跟 end, start指向-5,end 指向 10, 因為-7-5+10=-2, 故表示-5不可能和-7同時出現在一組內,因為10已經是目前最大,都還不足以將其變成大於零,故將start右移,依此類推,即可遍歷所有情況,然而此題還有一難點,就是如何去除重複答案,我是用map來達成任務,複雜度主要由指標移動貢獻,由於掃過n個數,每個數兩個指標移動為1~n-3,故複雜度為O(1+2+...+n-3)=
$O(n^2)$


p.s. 此題有更快算法,但非常複雜,請見連結
https://arxiv.org/abs/1404.0799


c++ code如下:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int len=nums.size();
        map<vector<int>,int> ans;
        for(int i=0;i<len-2;i++)
        {
            if(nums[i]==nums[i-1]&&i)
                continue;
            int start=i+1;
            int end=len-1;
            while(start!=end)
            {
                if(nums[start]+nums[end]+nums[i]==0)
                {
                    vector<int>temp;
                    temp.push_back(nums[i]);
                    temp.push_back(nums[start]);
                    temp.push_back(nums[end]);
                    if(!ans.count(temp))
                        ans.insert(make_pair(temp,0));
                    start++;
                }
                else if(nums[start]+nums[end]+nums[i]<0)
                    start++;
                else
                    end--;
            }
        }
        vector<vector<int>> ans1;
        map<vector<int>,int>::iterator it;
        for(it=ans.begin();it!=ans.end();it++)
        {
            ans1.push_back(it->first);
        }
        return ans1;
    }
};