給定一個(gè)整型向量，找出所有的三元組使之和為0（不允許重復(fù)）。
思路1：第一反應(yīng)是一道動(dòng)態(tài)規(guī)劃問(wèn)題。如果采用三層循環(huán)來(lái)查找的話(huà)，復(fù)雜度會(huì)達(dá)到n^3，這也許能完成一兩次操作，但應(yīng)該無(wú)法通過(guò)提交。事實(shí)上，三個(gè)數(shù)相加為0，必定有一個(gè)大于0和一個(gè)小于0的數(shù)字，應(yīng)當(dāng)能節(jié)省部分時(shí)間。是否可以轉(zhuǎn)換成在兩個(gè)數(shù)組中，尋找出一個(gè)數(shù)，使得另一個(gè)數(shù)組中存在兩數(shù)之和相等？這就變成了第一題。只要在外圈再套一層循環(huán)就好了。
ps 這里又出現(xiàn)了一個(gè)問(wèn)題，0怎么辦？假設(shè)存在三個(gè)0，則0 0 0應(yīng)當(dāng)是一種情況。目前的解決方案是認(rèn)為0既是正數(shù)又是復(fù)數(shù)。?利用find函數(shù)，尋找到第一個(gè)0，并將其歸入到neg中，剩下如果有多的0都?xì)w入pos。
pps 如何防止重復(fù)呢？假設(shè)存在1 1 1 -2 如果我們單純的尋找，那么肯定會(huì)認(rèn)為三個(gè)1是不同的1，實(shí)際上只要把多于三個(gè)的重復(fù)數(shù)字都消減到兩個(gè)即可（注意0除外！?。。?。
這樣看下來(lái)，這個(gè)方法的前置準(zhǔn)備工作是不是過(guò)多了點(diǎn)？況且，每一個(gè)數(shù)都要建立一個(gè)map 對(duì)內(nèi)存的開(kāi)銷(xiāo)也比較大。
思路2：利用指針，第一步還是一樣需要對(duì)原先的數(shù)組進(jìn)行排序。利用 i l r 三個(gè)指針來(lái)表示三元組。如果指針 i 指向了相同的值，則直接跳過(guò)后面的值， 如1 1 1 時(shí)，我們只考慮第一個(gè)1。l指向i之后，r指向末尾，將三者相加，判斷和的大小，如果和大于0 則r需要前移，反之l后移，如果剛好為0就存著。但是要注意，如果l 和 r 有多個(gè)重復(fù)值那么我們就得跳過(guò)他們才行。還要注意的一點(diǎn)是 0 0 0 時(shí)，如果我們l r 都存完了，但是此時(shí)l 和 r 的附近還是相同的，如果再繼續(xù) l++ 則這時(shí)候l就指向最后的0的，再判斷立馬溢出。同理 r 也要判斷。
