題目描述
給定一個整數(shù)列表秸仙，請問能否從中找出所有滿足a + b + c = 0的三元組袋坑？
例如，給定[-1, 0, 1, 2, -1, -4]优幸，那么答案為[[-1, 0, 1], [-1, -1, 2]]吨拍。
從2Sum說起
我們看一個簡化的問題：如果給定整數(shù)列表中，有且僅有一個 a + b = 0 的二元組网杆，那么該怎么求這個a和b呢羹饰？
思路很簡單：我們設(shè)置一個字典，字典的key代表待尋找的數(shù)跛璧，key和value對應(yīng)為二元組严里。
那么接下來，我們只需要遍歷整個列表追城。對于遍歷到的數(shù)num：
- 如果
num在字典里刹碾，那就找到了。
- 否則座柱，我們令
key為0 - num迷帜，value為num物舒。
于是代碼就是：
class Solution:
def twoSum(self, nums, target):
d = {}
nlen = len(nums)
i = 0
while i != nlen:
if nums[i] in d:
return [d[nums[i]],i]
else:
d[target - nums[i]] = i
i += 1
基于2Sum的3Sum
有了2Sum的鋪墊，只需要找到把3Sum問題轉(zhuǎn)化為2Sum問題的方法就好了戏锹。這個方法的思想是這樣的：
- 首先冠胯，我們對整數(shù)列表
nums進(jìn)行排序。這可以幫助我們簡化思路锦针。 - 然后荠察，遍歷
nums。 - 我們設(shè)遍歷到的位置為
fixpt奈搜。那么悉盆，現(xiàn)在的任務(wù)就是，在fixpt + 1到len(nums) - 1這個區(qū)間內(nèi)馋吗，尋找到a + b = 0 - nums[fixpt]的二元組就可以了焕盟。
先來看看代碼：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
#無解的情況有三個：元素個數(shù)不足，元素都大于或小于0宏粤。所以可以直接返回空列表脚翘。
if len(nums) < 2 or nums[0] > 0 or nums[-1] < 0: return []
ans = []
fixpt = 0
nlen = len(nums)
while fixpt < nlen - 2:
#這里是兩個簡化條件：
#第一，如果fixpt指向的數(shù)都大于0了绍哎，那么剩下的數(shù)肯定都大于0了
#第二来农，當(dāng)我們在當(dāng)前的fixpt搜索完畢，那么也就是fixpt+1到nlen的所有解都被我們搜索完了蛇摸。
#因此备图，如果fixpt+1指向的數(shù)和fixpt的相等，那么fixpt+2到nlen的可行解
#當(dāng)然也已經(jīng)被fixpt時的搜索找到了赶袄。
#所以才可以有這個直接跳過的步驟揽涮。
if nums[fixpt] > 0: break
if fixpt > 0 and nums[fixpt] == nums[fixpt - 1]:
fixpt += 1
continue
mpt = fixpt + 1
d = {}
qd = {}
#d的作用和2Sum時一樣。
#qd的作用是為了省去查找解重復(fù)的時間饿肺。
while mpt != nlen:
mptn = nums[mpt]
#下面這個if就是在判斷當(dāng)前數(shù)是否為d的key了蒋困。
if mptn in d and (nums[fixpt],mptn) not in qd:
ans.append([nums[fixpt], d[mptn], mptn])
qd[(nums[fixpt],mptn)] = True
#而這個if則是添加key。
elif 0 - nums[fixpt] - mptn not in d:
d[0 - nums[fixpt] - mptn] = mptn
mpt += 1
fixpt += 1
return ans
總的核心就在最后那部分敬辣。前面的部分大多是簡化時間的雪标。
最終，LeetCode上運行的時間大約在1200+ms溉跃。
雙指針法對可行解搜索的簡化
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
if len(nums) == 0 or nums[0] > 0 or nums[-1] < 0: return []
ans = []
pt = 0
while pt < len(nums) - 2:
if nums[pt] > 0: break
if pt > 0 and nums[pt] == nums[pt - 1]:
pt += 1
continue
left = pt + 1
right = len(nums) - 1
while left < right:
if nums[pt] + nums[left] + nums[right] == 0:
ans.append([nums[pt], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]: left += 1
while left < right and nums[right] == nums[right - 1]: right -= 1
left += 1
right -= 1
elif nums[pt] + nums[left] + nums[right] > 0:
right -= 1
else:
left += 1
pt += 1
return ans
在這個算法中村刨，前面的簡化部分依然沒有什么變化，但是在可行解搜索的部分撰茎，用了速度更快的雙指針法嵌牺。
它的思想是這樣的，首先fixpt這里改叫pt，依然是一個定點逆粹，用來提供2Sum查找的目標(biāo)募疮。
但是，現(xiàn)在有兩個指針僻弹，left和right阿浓，從兩邊逐漸往中間縮，根據(jù)查找到的三數(shù)和決定是移動left還是移動right蹋绽。
具體到代碼上芭毙，縮的策略是這樣的：
while left < right:
# 若滿足了a+b+c=0的條件，那么當(dāng)然就記錄答案了
if nums[pt] + nums[left] + nums[right] == 0:
ans.append([nums[pt], nums[left], nums[right]])
#這里指針的再次移動是很關(guān)鍵的蟋字，不能用break代替
#因為可行解可能不止一個稿蹲，在內(nèi)部還可能有別的可行解扭勉，所以跳過同類數(shù)字后再次進(jìn)入大循環(huán)查找鹊奖。
while left < right and nums[left] == nums[left + 1]: left += 1
while left < right and nums[right] == nums[right - 1]: right -= 1
left += 1
right -= 1
#如果a+b+c>0，那么說明nums[left] + nums[right]的總和偏大涂炎，所以應(yīng)當(dāng)減小大數(shù)忠聚，即right -= 1。
elif nums[pt] + nums[left] + nums[right] > 0:
right -= 1
#同樣的道理唱捣，只不過是為了讓總和增大两蟀。
else:
left += 1
最后調(diào)整總和大小還好理解，但是那兩行while是用來干什么的呢震缭？
舉個例子赂毯，就是[-1, 0, 1, 2, -1, -4]吧。排序之后拣宰，這個列表是[-4, -1, -1, 0, 1, 2]党涕。-4顯然沒有對應(yīng)項，但是對于第一個-1巡社，在這個算法下膛堤，第一個找到的可行解是[-1,-1,2]。然而晌该，如果就這么break了肥荔，就會丟失[0, 1]這個部分的搜索，而這部分恰恰是和-1能組成可行解朝群。
這個算法的時間大概是1000ms+燕耿。
正負(fù)數(shù)配對
在定點的思想下，暴力一點的解法就是在定點之后的搜索區(qū)間內(nèi)進(jìn)行配對了姜胖。這樣的方法肯定是比優(yōu)化過的方法慢一些的誉帅，因為這已經(jīng)接近n^2了，而雙指針只需要n的時間。
然而堵第，這種n^2的配對用得好的話吧凉，效果也是不錯的。我們可以分析一下這個問題：要滿足a + b + c = 0踏志，需要滿足什么條件阀捅？
- 如果沒有0或者有一個數(shù)是0，那么必然需要有兩個數(shù)一正一負(fù)针余。
- 如果有兩個數(shù)是0饲鄙，那么第三個也必須是0。
由此我們可以構(gòu)思圆雁，如果我們將正數(shù)忍级、負(fù)數(shù)、0分別歸入集合伪朽，并對數(shù)字進(jìn)行計數(shù)處理轴咱，那么就可以這么做：
- 若0的個數(shù)大于2，那么可行解必然有
[0, 0, 0]烈涮。 - 我們從正數(shù)和負(fù)數(shù)中各取一個數(shù)朴肺，然后計算我們的目標(biāo)，比如說坚洽，取了
x和y兩個數(shù)戈稿，那么需要尋找的就是s = -(x + y)。- 有可能
s == x or s == y讶舰。不妨設(shè)s == x鞍盗，那么只要看x的個數(shù)是否大于1，若如此跳昼，則有可行解[x, x, y]般甲。對于s == y的情況也類似。 - 如果不等庐舟，那么我們只需要在
x < s < y的時候欣除，以[x, s, y]作為我們的可行解。因為挪略，接下來的配對历帚，可能會選到數(shù)對s和y，那么再計算的時候杠娱，x就成了我們的目標(biāo)挽牢。既然三個數(shù)必然存在x < s < y關(guān)系，那么我們就只在這個關(guān)系滿足的時候視為可行解摊求，這樣就避免了重復(fù)添加可行解的麻煩禽拔。
- 有可能
分析完了，代碼是這樣的：
class Solution:
def threeSum(self, nums):
d = {}
for val in nums:
d[val] = d.get(val, 0) + 1
pos = [x for x in d if x > 0]
neg = [x for x in d if x < 0]
res = []
if d.get(0, 0) > 2:
res.append([0, 0, 0])
for x in pos:
for y in neg:
s = -(x + y)
if s in d:
if s == x and d[x] > 1:
res.append([x, x, y])
elif s == y and d[y] > 1:
res.append([x, y, y])
elif y < s < x:
res.append([x, y, s])
return res
這里的一個巧妙的操作細(xì)節(jié)是，先用字典得到所有不重復(fù)的數(shù)字睹栖，以及出現(xiàn)的次數(shù)硫惕。然后就很好處理了。
既簡捷又快速野来。這個LeetCode的樣例得分是320ms恼除。
任意值3Sum算法的特殊情況
在LeetCode上最快的解法，有很多數(shù)字技巧曼氛，有些地方我也沒琢磨透豁辉。具體是這樣的：
class Solution:
def threeSum(self, nums: 'List[int]') -> 'List[List[int]]':
from bisect import bisect_left, bisect_right
target = 0
result = []
length = len(nums)
if length < 3:
return result
count ={}
# map the counts
for n in nums:
if n in count:
count[n] += 1
else:
count[n] = 1
keys = list(count.keys())
keys.sort()
t3 = target // 3
if t3 in keys and count[t3] >= 3:
result.append([t3, t3, t3])
begin = bisect_left(keys, target - keys[-1] * 2)
end = bisect_left(keys, target * 3)
for i in range(begin, end):
a = keys[i]
if count[a] >= 2 and target - 2 * a in keys:
result.append([a, a, target - 2 * a])
max_b = (target - a) // 2 # target-a is remaining
min_b = target - a - keys[-1] # target-a is remaining and c can max be keys[-1]
b_begin = max(i + 1, bisect_left(keys, min_b))
b_end = bisect_right(keys, max_b)
for j in range(b_begin, b_end):
b = keys[j]
c = target - a - b
if c in count and b <= c:
if b < c or count[b] >= 2:
result.append([a, b, c])
return result
先解釋一下，bisect是二分查找?guī)煲ɑ迹琹eft和right的含義可以自己查查徽级，很好理解。
首先明確一下聊浅，3Sum問題的解一共四類：
-
[0, 0, 0]餐抢，三數(shù)相等。 -
[a, a, b]狗超； -
[a, b, b]弹澎，以上2和3都有a < b。 -
[a, b, c]努咐，a < b < c。
下面我們會拿這個序號來指代解的類型殴胧。
我們一步步來分析：
target = 0
這一行就已經(jīng)表明了這是一個通用的3Sum算法渗稍，可以用來算任意target = a + b + c值的3Sum。
然后是計數(shù)部分：
count ={}
# map the counts
for n in nums:
if n in count:
count[n] += 1
else:
count[n] = 1
這里的計數(shù)和上面正負(fù)配對法的
d = {}
for val in nums:
d[val] = d.get(val, 0) + 1
部分是一樣的喻频。
然后代碼就有趣起來了：
keys = list(count.keys())
keys.sort()
t3 = target // 3
if t3 in keys and count[t3] >= 3:
result.append([t3, t3, t3])
為什么要這么算t3呢有梆？我沒看懂這里整數(shù)除法的意思盾鳞，不過對于我們target == 0的情況，可以直接簡化為0的個數(shù)是否大于等于3拱燃。也就是，判斷第一種解存不存在力惯。
然后就是很巧妙的搜索范圍簡化：
begin = bisect_left(keys, target - keys[-1] * 2)
end = bisect_left(keys, target * 3) #might use target // 3
for i in range(begin, end):
a = keys[i]
if count[a] >= 2 and target - 2 * a in keys:
result.append([a, a, target - 2 * a])
在這里碗誉，我們要規(guī)定a，三元組最小數(shù)的搜索范圍父晶。
begin的查找參數(shù)哮缺，意味著就算我們用兩個最大的數(shù)keys[-1]來構(gòu)成可行解，那么最小的數(shù)也只能是target - keys[-1] * 2甲喝。
而end的查找參數(shù)（我認(rèn)為這里應(yīng)該用整數(shù)除法尝苇，實際上這么改之后也ac了），它意味著最小數(shù)的最大值也不能超過t3，不然作為三元組的最小數(shù)糠溜，三個a相加都已經(jīng)超出target了淳玩。
下一步就是在可行的a中，看看有沒有可行的第二種解非竿。
懂了a的范圍處理方式之后凯肋，b的范圍處理自然也好理解了，而且方法也印證了上面 說的end參數(shù)要用整數(shù)除法的修改汽馋。
max_b = (target - a) // 2 # target-a is remaining
min_b = target - a - keys[-1] # target-a is remaining and c can max be keys[-1]
b_begin = max(i + 1, bisect_left(keys, min_b))
b_end = bisect_right(keys, max_b)
一旦我們確定了a和b侮东，那么c也就自然確定了：
for j in range(b_begin, b_end):
b = keys[j]
c = target - a - b
if c in count and b <= c:
if b < c or count[b] >= 2:
result.append([a, b, c])
由于b和c可能在搜索過程中逆序出現(xiàn)，因此我們就用b <= c的方法確定什么時候確定可行解豹芯。
最后這里if b < c or count[b] >= 2:的邏輯也有點巧妙悄雅，先判斷b < c是否成立，如果我們需要判斷count[b] >= 2铁蹈，那么就暗含了 c == b宽闲。
前者找出了第四種解，后者找出了第三種解握牧。那么這樣容诬，四種可能的解的類型都被我們找完了。
由此整個代碼就分析結(jié)束沿腰，它的條理非常清楚览徒，速度也很快， 在最快的情況下可以達(dá)到280ms颂龙。
4Sum习蓬？
這個就留到下次再說了，哈哈~
