當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

LeetCode——15. 3Sum

發(fā)布時(shí)間：2025/7/14 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 LeetCode——15. 3Sum 小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

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

二.題目大意：

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

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

三.題解：

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

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

方法1：利用哈希表

這種方法的基本思想是，將數(shù)組中每個(gè)元素和它的下標(biāo)構(gòu)成一個(gè)鍵值對(duì)存入到哈希表中，在尋找的過程中對(duì)于數(shù)組中的某兩個(gè)元素a、b只需在哈希表中判斷是否存在-a-b即可，由于在哈希表中的查找操作的時(shí)間復(fù)雜度為O(1)，在數(shù)組中尋找尋任意的找兩個(gè)元素a、b需要O(n^2)，故總的時(shí)間復(fù)雜度為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());//排序是為了不重復(fù)處理后續(xù)重復(fù)出現(xiàn)的元素for(int i = 0; i < len; i++){if(i != 0 && num[i] == num[i - 1])//i重復(fù)出現(xiàn)時(shí)不重復(fù)處理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重復(fù)出現(xiàn)時(shí)不重復(fù)處理j++;}_map.insert({num[j],j});//注意_map插入的元素是根據(jù)j來的不是根據(jù)i來的}}return rs;}};

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

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

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

2.關(guān)于對(duì)三元組進(jìn)行去重，實(shí)際上有兩種方式：

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

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

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

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

方法2：利用兩個(gè)指針

這種方法是最常用的方法(leetcode上AC的代碼大多都是這種方法)，主要的思想是：必須先對(duì)數(shù)組進(jìn)行排序(不排序的話，就不能利用雙指針的思想了，所以說對(duì)數(shù)組進(jìn)行排序是個(gè)大前提)，每次固定i的位置，并利用兩個(gè)指針j和k，分別指向數(shù)組的i+1位置和數(shù)組的尾元素，通過判斷num[j]+num[k]與-num[i]的大小，來決定如何移動(dòng)指針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])//如果遇到重復(fù)元素的情況，避免多次考慮continue;while(j < k)//對(duì)于每一個(gè)num[i]從i之后的元素中,尋找對(duì)否存在三者之和為0的情況{if(num[i] + num[j] +num[k] == 0)//當(dāng)三者之和為0的情況{rs.push_back({num[i],num[j],num[k]});j++;//當(dāng)此處的j,k滿足時(shí)，別忘了向前/向后移動(dòng)，判斷下一個(gè)是否也滿足k--;while(j < k && num[j] == num[j - 1])//如果遇到j(luò)重復(fù)的情況，也要避免重復(fù)考慮j++;while(j < k && num[k] == num[k + 1])//如果遇到k重復(fù)的情況，也要避免重復(fù)考慮k--;}else if(num[i] + num[j] + num[k] < 0)//三者之和小于0的情況，說明num[j]太小了，需要向后移動(dòng)j++;else//三者之和大于0的情況，說明num[k]太大了，需要向前移動(dòng)k--;}}return rs;}};

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

1.需要先對(duì)數(shù)組進(jìn)行排序，一開始的時(shí)候也強(qiáng)調(diào)了，不排序的話整個(gè)思路就是錯(cuò)的；這種方法的一切都是建立在有序數(shù)組的前提下。

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

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

(1)i指針的去重同方法1一樣，都是判斷當(dāng)前位置的元素與前一個(gè)位置的元素是否相同，如果相同，就忽略。這是因?yàn)榍耙粋€(gè)位置的元素已經(jīng)處理過了，如果當(dāng)前位置的元素與之相同的話，就沒必要處理了，否則就會(huì)造成重復(fù)。

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

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

在分析下方法2：

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

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

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

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

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

1.利用雙指針。

2.利用哈希表。

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

注：對(duì)于Ksum問題，如果題目要求結(jié)果不能重復(fù)的話，一定要考慮去重，去重方法，上面第一個(gè)例子也講了。

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

可參考：

　　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

轉(zhuǎn)載于:https://www.cnblogs.com/wangkundentisy/p/9079622.html