一.題目鏈接：https://leetcode.com/problems/3sum/

二.題目大意：

　3和問題是一個比較經(jīng)典的問題，它可以看做是由2和問題(見http://www.cnblogs.com/wangkundentisy/p/7525356.html)演化而來的。題目的具體要求如下：

給定一個數(shù)組A，要求從A中找出這么三個元素a,b,c使得a + b + c = 0，返回由這樣的a、b、c構成的三元組，且要保證三元組是唯一的。(即任意的兩個三元組，它們里面的元素不能完全相同)

三.題解：

　　我們知道3和問題是由2和問題演化而來的，所以說我們可以根據(jù)2和問題的求法，來間接求解三和問題。常見的2和問題的求解方法，主要包括兩種那：利用哈希表或者兩用雙指針。

而三和問題，我們可以看成是在2和問題外面加上一層for循環(huán)，所以3和問題的常用解法也是分為兩種：即利用哈希表和利用雙指針。下面具體介紹兩種方法：

方法1：利用哈希表

這種方法的基本思想是，將數(shù)組中每個元素和它的下標構成一個鍵值對存入到哈希表中，在尋找的過程中對于數(shù)組中的某兩個元素a、b只需在哈希表中判斷是否存在-a-b即可，由于在哈希表中的查找操作的時間復雜度為O(1)，在數(shù)組中尋找尋任意的找兩個元素a、b需要O(n^2)，故總的時間復雜度為O(N^2)。代碼如下:

class Solution { public:vector<vector<int> > threeSum(vector<int> &num){vector<vector<int>> rs;int len = num.size();if(len == 0)return rs;sort(num.begin(),num.end());//排序是為了不重復處理后續(xù)重復出現(xiàn)的元素for(int i = 0; i < len; i++){if(i != 0 && num[i] == num[i - 1])//i重復出現(xiàn)時不重復處理continue;unordered_map<int,int> _map;//注意建立_map的位置for(int j = i + 1; j < len; j++){if(_map.find(-num[i]-num[j]) != _map.end()){rs.push_back({num[i],num[j],-num[i]-num[j]});while(j + 1 < len && num[j] == num[j + 1])//j重復出現(xiàn)時不重復處理j++;}_map.insert({num[j],j});//注意_map插入的元素是根據(jù)j來的不是根據(jù)i來的}}return rs;}};

這種方法先對數(shù)組nums進行排序，然后在雙重for循環(huán)中對哈希表進行操作，時間復雜度為O(N*logN)+O(N^2)，所以總的時間復雜度為O(N^2)，空間復雜度為O(N)，典型的以時間換空間的策略。但是，有幾個重要的點一定要掌握：

1.為什么要事先對數(shù)組nums進行排序？

這是因為由于題目要求的是返回的三元組必須是重復的，如果直接利用哈希表不進行特殊處理的話，最終的三元組一定會包含重復的情況，所以我們對數(shù)組進行排序是為了對最終的結果進行去重，其中去重包括i重復的情況和j重復的情況分，不注意兩種情況的處理方式是不同的，i是判斷與i-1是否相同；而j是判斷與j+1是否相同。

2.關于對三元組進行去重，實際上有兩種方式：

(1)按照本例中的形式，先對數(shù)組進行排序，在遍歷的過程中遇到重復元素的情況就跳過。

(2)不對數(shù)組事先排序，在遍歷過程中不進行特殊的處理，在得到整個三元組集合后，在對集合中的三元組進行去重，刪去重復的三元組。(一個簡單的思路是對集合中每個三元組進行排序，然后逐個元素進行比較來判斷三元組是否重復)。(這種思路可能會比本例中的方法性能更優(yōu)一些)

3.注意哈希表建立的位置，是首先確定i的位置后，才開始創(chuàng)建哈希表的；而不是先建立哈希表，再根據(jù)i和j進行遍歷。此外，哈希表中存儲的元素是根據(jù)j的位置來決定的，相當于每次先固定一個i，然后建立一個新的哈希表，然后在遍歷j，并根據(jù)j判斷哈希表。(這個過程并不難理解，自己舉個例子，畫個圖應該就明白了)

然而，我利用這種方法(上述代碼)，在leetcode上提交居然超時了！！！即方法1在leetcode沒通過啊。

方法2：利用兩個指針

這種方法是最常用的方法(leetcode上AC的代碼大多都是這種方法)，主要的思想是：必須先對數(shù)組進行排序(不排序的話，就不能利用雙指針的思想了，所以說對數(shù)組進行排序是個大前提)，每次固定i的位置，并利用兩個指針j和k，分別指向數(shù)組的i+1位置和數(shù)組的尾元素，通過判斷num[j]+num[k]與-num[i]的大小，來決定如何移動指針j和k，和leetcode上最大容器的拿到題目的思想類似。具體代碼如下：

class Solution { public:vector<vector<int> > threeSum(vector<int> &num){vector<vector<int>> rs;int len = num.size();if(len == 0)return rs;sort(num.begin(),num.end());for(int i = 0; i < len; i++){int j = i + 1;int k = len - 1;if(i != 0 && num[i] == num[i - 1])//如果遇到重復元素的情況，避免多次考慮continue;while(j < k)//對于每一個num[i]從i之后的元素中,尋找對否存在三者之和為0的情況{if(num[i] + num[j] +num[k] == 0)//當三者之和為0的情況{rs.push_back({num[i],num[j],num[k]});j++;//當此處的j,k滿足時，別忘了向前/向后移動，判斷下一個是否也滿足k--;while(j < k && num[j] == num[j - 1])//如果遇到j重復的情況，也要避免重復考慮j++;while(j < k && num[k] == num[k + 1])//如果遇到k重復的情況，也要避免重復考慮k--;}else if(num[i] + num[j] + num[k] < 0)//三者之和小于0的情況，說明num[j]太小了，需要向后移動j++;else//三者之和大于0的情況，說明num[k]太大了，需要向前移動k--;}}return rs;}};

　　

該方法的時間復雜度為O(N*logN)+O(N^2)=O(N^2)和方法1實際上是一個數(shù)量級的，但是空間復雜度為O(1)，所以說綜合比較的話，還是方法2的性能更好一些。同樣地，這種方法也有幾個需要注意的點：

1.需要先對數(shù)組進行排序，一開始的時候也強調了，不排序的話整個思路就是錯的；這種方法的一切都是建立在有序數(shù)組的前提下。

2.每次找到符合條件的num[j]和num[k]時，這時候，j指針要往前移動一次，同時k指針向后移動一次，避免重復操作，從而判斷下個元素是否也符合

3.和方法1一樣，都需要去重(且去重時，一般都是在找到滿足條件的元素時才執(zhí)行)，由于該方法一定要求數(shù)組是有序的，所以就按照第一種去重方法來去重就好了。但是需要注意下與第1種方法去重的不同之處：

(1)i指針的去重同方法1一樣，都是判斷當前位置的元素與前一個位置的元素是否相同，如果相同，就忽略。這是因為前一個位置的元素已經(jīng)處理過了，如果當前位置的元素與之相同的話，就沒必要處理了，否則就會造成重復。

(2)j指針(還有k指針)的去重方法同方法1是不同的。先分析下方法1：

如果num[j]是符合條件的元素的話，并且下一個元素同num[j]相同的話，那么久沒必要再去判斷了，直接跳過就行了。那如果把nums[j] == num[j +1]改成num[j] == num[j -1]行嗎？顯然不行啊，舉個例子就行，假如num[j] == 1且此時1正好符合，那么對于序列1,1....的話，當判斷第一個1時，會把結果存入數(shù)組；如果改成num[j] == num[j-1]的話，判斷第二個1的時候，會先把元素存入數(shù)組，然后再判斷和前一個元素是否相同；即實際上這樣已經(jīng)發(fā)生重復操作了，如果是nums[j] == num[j +1]就是直接判斷下一個元素，就是先判斷在存儲，就不會重復操作了。(也可以這樣理解：由于去重操作只在找到重復元素的時候才進行，當num[j]滿足時，如果num[j+1]也滿足，則一定不用再判斷了；而如果num[j-1]與num[j]相同的話，反而會把num[j-1]和num[j]都存進去了)

在分析下方法2：

對于方法2中的j指針和k指針，就比較好理解了；由于在判斷是滿足條件的元素的話，就會j++,k--，此時j和k的位置都發(fā)生了變化，就不知道是不是滿足了，所以要根據(jù)前一個元素來判斷，如果現(xiàn)在的元素與前一個元素(對于j來說就是j-1，對于k來說就是K+1)相同的話，就直接跳過，從而避免了重復操作。

與方法1中的j是不同的，方法1中的j并沒有執(zhí)行j++操作(或者說是后執(zhí)行的j++)。

方法2最終在leetcode上AC了，以后還是優(yōu)先使用這種的方法吧！

?=======================================================分割線======================================================================================

　　以上問題都是針對2sum和3sum，那么對于4sum。。。ksum，上述解法也是可行的。所以對于Ksum問題來講，通常有兩種思路：

1.利用雙指針。

2.利用哈希表。

這兩種方法的本質都是，在外層有k-2層循環(huán)嵌套，最內層循環(huán)中采用雙指針或者哈希表，所以總的時間復雜度為O(N^k-1)。

注：對于Ksum問題，如果題目要求結果不能重復的話，一定要考慮去重，去重方法，上面第一個例子也講了。

實際上，對于4sum問題，還有更優(yōu)的解法。主要是利用哈希表，其中哈希表類為<int,vector<pair<int,int>>>型，其中key表示的是數(shù)組中任意來年各個元素的和，value表示的這兩個元素對應下標構成的pair，即pair<i,j>，由于對于兩組不同的元素(共4個)可能存在重復的和，即key值相同，所以value對應的是一個pair構成的數(shù)組。這樣的話，后面只需要兩次循環(huán)找出hash[target - num[i] - num[j]]即可，所以總的時間復雜為O(N^2),空間復雜度也為O(N^2)。(由于pair<int,int>本質就是個哈希表，所以這種方法的實質就是嵌套哈希表)

可參考：

　　https://blog.csdn.net/nanjunxiao/article/details/12524405

　　https://www.cnblogs.com/TenosDoIt/p/3649607.html

　　https://blog.csdn.net/haolexiao/article/details/70768526

　　http://westpavilion.blogspot.com/2014/02/k-sum-problem.html

轉載于:https://www.cnblogs.com/wangkundentisy/p/9079622.html

總結

以上是生活随笔為你收集整理的LeetCode——15. 3Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。