1 題目描述

2 解題思路

2.1 使用兩數(shù)之和函數(shù)

這種做法目前超時了，如果大家有想到合適的減時間/剪枝的方法，歡迎私信or評論~

兩數(shù)之和的方法見文巾解題 1. 兩數(shù)之和_劉文巾的博客-CSDN博客

我的思路是這樣的，先固定一個數(shù)x，然后另外兩個數(shù)就需要和為-x，那么兩數(shù)之和為-x就可以調用之前的函數(shù)。

不過唯一不同的是，之前的“兩數(shù)之和”，只要求出一組解就可以了，但我們這里需要的是全部解。

所以我對“兩數(shù)之和”中的函數(shù)進行了一點改造。當我們找到滿足條件的兩個數(shù)時，我不直接返回。而是將這組解放到一個list中。等所有的元素都遍歷完了，所有滿足條件的解都放到這個list中了。那么把這個list返回，就是和等于這個-x的所有數(shù)對了。

?

然后我們對每一個數(shù)對，將x拼接進去。得到一組滿足條件的“三數(shù)組合”。

?

但這時候“三數(shù)組合”會有冗余的。我們需要去重。我現(xiàn)在的思路是，將“三數(shù)組合”排序，然后轉換成元組tuple，之后使用set（list不能應用于set上，tuple可以）

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:ret=[]for i in range(len(nums)):x=nums[i]y=target-xif(y in nums):if(i==nums.index(y)):continueelse:ret.append([x,y])return(ret) #文巾解題1 兩數(shù)之和代碼 稍作改動def threeSum(self, nums: List[int]) -> List[List[int]]:ret=[]l=len(nums)s=set(nums) #不同的“和”for i in s:tmp=self.twoSum(nums[0:nums.index(i)]+nums[nums.index(i)+1:l],-i) #找所有滿足條件的“兩數(shù)組合”if(tmp==[]):continueelse:for j in tmp:j.extend([i])j.sort()ret.append(tuple(j)) #所有滿足條件的“三數(shù)組合” return (list(set(ret))) #結果去重

2.2 排序 + 雙指針（leetcode方法）

題目中要求找到所有不重復且和為 0 的三元組，這個不重復的要求使得我們無法簡單地使用三重循環(huán)枚舉所有的三元組。

這是因為在最壞的情況下，數(shù)組中的元素全部為 0。任意一個三元組的和都為 0。如果我們直接使用三重循環(huán)枚舉三元組，會得到 O(N^3)個滿足題目要求的三元組（其中 N?是數(shù)組的長度）時間復雜度至少為 O(N^3)。在這之后，我們還需要使用哈希表進行去重操作，得到不包含重復三元組的最終答案，又消耗了大量的空間。這個做法的時間復雜度和空間復雜度都很高，因此我們要換一種思路來考慮這個問題。

?

不重復的本質是什么？我們保持三重循環(huán)的大框架不變，只需要保證：

第二重循環(huán)枚舉到的元素不小于當前第一重循環(huán)枚舉到的元素；

第三重循環(huán)枚舉到的元素不小于當前第二重循環(huán)枚舉到的元素。

?

也就是說，我們枚舉的三元組 (a, b, c)滿足 a≤b≤c，保證了只有 (a, b, c) 這個順序會被枚舉到，而 (b, a, c)、(c, b, a)等等這些不會，這樣就減少了重復。

要實現(xiàn)這一點，我們可以將數(shù)組中的元素從小到大進行排序，隨后使用普通的三重循環(huán)就可以滿足上面的要求。

?

同時，對于每一重循環(huán)而言，相鄰兩次枚舉的元素不能相同，否則也會造成重復。

舉個例子，如果排完序的數(shù)組為[0, 1, 2, 2, 2, 3]。

我們使用三重循環(huán)枚舉到的第一個三元組為 (0, 1, 2)，如果第三重循環(huán)繼續(xù)枚舉下一個元素，那么仍然是三元組 (0, 1, 2)，產生了重復。

因此我們需要將第三重循環(huán)「跳到」下一個不相同的元素，即數(shù)組中的最后一個元素 3，枚舉三元組 (0, 1, 3)。

?

下面給出了改進的方法的偽代碼實現(xiàn)：

nums.sort()
for first = 0 .. n-1
? ? // 只有和上一次枚舉的元素不相同，我們才會進行枚舉
? ? if first == 0 or nums[first] != nums[first-1] then
? ? ? ? for second = first+1 .. n-1
? ? ? ? ? ? if second == first+1 or nums[second] != nums[second-1] then
? ? ? ? ? ? ? ? for third = second+1 .. n-1
? ? ? ? ? ? ? ? ? ? if third == second+1 or nums[third] != nums[third-1] then
? ? ? ? ? ? ? ? ? ? ? ? // 判斷是否有 a+b+c==0
? ? ? ? ? ? ? ? ? ? ? ? check(first, second, third)

這種方法的時間復雜度仍然為 O(N^3)，畢竟我們還是沒有跳出三重循環(huán)的大框架。

然而它是很容易繼續(xù)優(yōu)化的，可以發(fā)現(xiàn)，如果我們固定了前兩重循環(huán)枚舉到的元素 a 和 b，那么只有唯一的 c 滿足 a+b+c=0。當?shù)诙匮h(huán)往后枚舉一個元素 b'時，由于 b' > b，那么滿a+b'+c'=0的 c'?一定有 c' < c，即 c'在數(shù)組中一定出現(xiàn)在 c?的左側。也就是說，我們可以從小到大枚舉 b，同時從大到小枚舉 c，即第二重循環(huán)和第三重循環(huán)實際上是并列的關系。（那么前面為代碼中c右側的遍歷部分就被剪枝剪掉了）

有了這樣的發(fā)現(xiàn)，我們就可以保持第二重循環(huán)不變，而將第三重循環(huán)變成一個從數(shù)組最右端開始向左移動的指針，從而得到下面的偽代碼（加粗的部分為兩者不同之處）：

nums.sort()
for first = 0 .. n-1

? // 只有和上一次枚舉的元素不相同，我們才會進行枚舉
? ? if first == 0 or nums[first] != nums[first-1] then
? ? ? ? // 第三重循環(huán)對應的指針
? ? ? ? third = n-1
? ? ? ? for second = first+1 .. n-1
? ? ? ? ? ? if second == first+1 or nums[second] != nums[second-1] then
? ? ? ? ? ? ? ? // 向左移動指針，直到 a+b+c 不大于 0
? ? ? ? ? ? ? ? while nums[first]+nums[second]+nums[third] > 0
? ? ? ? ? ? ? ? ? ? third = third-1
? ? ? ? ? ? ? ? // 判斷是否有 a+b+c==0
? ? ? ? ? ? ? ? check(first, second, third)

這個方法就是我們常說的「雙指針」。

當我們需要枚舉數(shù)組中的兩個元素時，如果我們發(fā)現(xiàn)隨著第一個元素的遞增，第二個元素是遞減的，那么就可以使用雙指針的方法，將枚舉的時間復雜度從 O(N^2)減少至 O(N)。

為什么時間復雜度是 O(N) 呢？這是因為在枚舉的過程每一步中，「左指針」會向右移動一個位置（也就是題目中的 bb），而「右指針」會向左移動若干個位置，這個與數(shù)組的元素有關，但我們知道它一共會移動的位置數(shù)為O(N)。

均攤下來，每次也向左移動一個位置，因此時間復雜度為 O(N)。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:n = len(nums)nums.sort()#對nums進行排序ans = list()# 枚舉 afor first in range(n):# 需要和上一次枚舉的數(shù)不相同if first > 0 and nums[first] == nums[first - 1]:continue#third 對應的指針初始指向數(shù)組的最右端third = n - 1target = -nums[first]#second和third指針指向的元素和為first指針指向的元素的相反數(shù)# 枚舉 bfor second in range(first + 1, n):# 需要和上一次枚舉的數(shù)不相同if second > first + 1 and nums[second] == nums[second - 1]:continue# c向左移動的時候，需要保證 b 的指針在 c 的指針的左側while second < third and nums[second] + nums[third] > target:third -= 1# 如果指針重合，隨著 b 后續(xù)的增加# 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)if second == third:breakif nums[second] + nums[third] == target:ans.append([nums[first], nums[second], nums[third]])return ans

?

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的文巾解题 15. 三数之和的全部內容，希望文章能夠幫你解決所遇到的問題。

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