這里寫幾個(gè)sum問題的總結(jié)。
首先是
leetcode 1：two sum
解法很簡單棘催，就是哈希表劲弦。哈希表的查找速度是O(1)，當(dāng)然是平均時(shí)間醇坝，最差是O(n)邑跪，對應(yīng)全部沖突。當(dāng)然，以python的dict為例画畅，dict是會擴(kuò)容的砸琅，擴(kuò)容的時(shí)候會rehash。所以這個(gè)時(shí)候的內(nèi)部也會O(n)一次轴踱。anyway症脂，不討論這個(gè)情況的話，確實(shí)是hash最快淫僻。因此我們的實(shí)現(xiàn)如下：
def two sum(nums, target):
d={}
for i, num in enumerate(nums):
# 需要注意的是摊腋，這里要以num作為key，index作為value嘁傀，只有這樣查詢的時(shí)候才是O(1)
if num in d:
return [i, d[num]]
# target-num作為key兴蒸，所以如果in 滿足的話就是當(dāng)前的num和target-num了
d[target-num]=i
leetcode 167:已經(jīng)排序的two sum
這個(gè)問題有意思在，已經(jīng)排好序了细办，那么哈希似乎顯得不夠靈活了橙凳，我們考慮，可以用一種叫做“雙指針”的東西笑撞，雙指針應(yīng)用及其廣岛啸，最牛逼的用法就是鏈表求環(huán)，堪稱天人茴肥。不過這里不說那個(gè)坚踩，我們認(rèn)為，首先把一個(gè)指針放在頭部瓤狐，另一個(gè)指向尾部瞬铸，然后如果大了就尾指針向內(nèi)，小了就頭指針向后础锐。也很簡單嗓节，如下：
def two sum2(nums, target):
i = 0
j = len(nums)-1
while i<j:
sums = nums[i]+nums[j]
if sums == target:
return [i+i, j+1] # 這里+1是因?yàn)樵}要求坐標(biāo)從1開始
elif sums > target:
j -= 1
else:
i += 1
leetcode 653:wo sum, Input is a BST
這道題是給的是一顆二叉樹，我們要找到target皆警，否則返回False拦宣。做法就是dfs一棵樹，而內(nèi)部這個(gè)查找的過程和two sum是一樣的信姓，為了快速鸵隧，我們用一個(gè)set（set和dict一樣都是hashable，查找速度O(1)）意推，這個(gè)set里保存target-root.val的值豆瘫，因此便利的時(shí)候只要val in s，就說明找到了左痢。同時(shí)靡羡，這樣保存還有一個(gè)好處系洛，如果真的只能保存一個(gè)值，那隨著我們遍歷略步，我們會不兔璩叮回溯，麻煩的一筆趟薄。而如果我們把候選都放到set里绽诚，每次只需看看需要的在不在就行了。第一題之所以用dict杭煎，是因?yàn)樾枰瑫r(shí)保存標(biāo)號和數(shù)值恩够，而這個(gè)只需要標(biāo)號就好，故而使用set羡铲。
def two sum4(root, target):
s = set()
return dfs(root, target, s)
def dfs(root, target, s):
if not root:
return False
if root.val in s:
return True
else:
s.add(target-root.val)
return dfs(root.left, target, s) or dfs(root.right, target, s)
leetcode34: 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
這道題個(gè)人認(rèn)為極佳蜂桶，如果以后我當(dāng)面試官，我一定會考這道題也切。這道題的時(shí)間要求是O(lg(n))扑媚，也就是說，不能有一般直接查找的操作雷恃。雖然很多提交時(shí)間很短疆股，但是都有找到點(diǎn)后兩側(cè)遍歷的操作，這種操作在大規(guī)模上必然會爆倒槐，能ac僅僅是lc的case太少了旬痹。
要我來解，必然只能純查找讨越，也就是两残，找到起點(diǎn)，找到終點(diǎn)谎痢。binary search的模板已經(jīng)很清晰了磕昼，看起來大了就減end，小了就加start的操作似乎也不能改變节猿，故能變的也就是==的情況了
假設(shè)尋找第一個(gè)，那么當(dāng)mid<target時(shí)漫雕，我們正常start右移滨嘱，mid+1。如果大于浸间，那么end左移太雨，mid-1，可是如果==魁蒜？這里不會return囊扳，而是繼續(xù)縮小右邊界（即吩翻，end左移），反之锥咸，start右移狭瞎。
class Solution(object):
def searchRange(self, nums, target):
start=self.findfirst(nums,target)
end=self.findlast(nums,target)
return [start,end]
def findfirst(self,nums,target):
l=0
r=len(nums)-1
index=-1
while(l<=r):
mid=l+(r-l)//2
if nums[mid]<target:
l=mid+1
else:
r=mid-1
if nums[mid]==target:
index=mid
return index
def findlast(self,nums,target):
l=0
r=len(nums)-1
index=-1
while(l<=r):
mid=l+(r-l)//2
if nums[mid]<=target:
l=mid+1
else:
r=mid-1
if nums[mid]==target:
index=mid
return index
明白了這個(gè)之和，代碼就變得很簡單搏予，也可以把兩個(gè)融合到一起熊锭，但是沒有必要。
leetcode 15:三數(shù)之和
這個(gè)題其實(shí)也是雙指針雪侥，不過因?yàn)橛?個(gè)數(shù)碗殷，所以需要第3個(gè)指針來控制遍歷，其余的和已排序的2sum一樣速缨。之所以一樣锌妻，是因?yàn)閷τ贠(n^2)的復(fù)雜度而言，排序的O(nlgn)不算太過分：
def threesum(nums): # 這道題需要求出三數(shù)和為0
nums.sort()
# i = 0
res=set()
for i in range(len(nums)-2):
j = i + 1
k = len(nums)-1
while j<k:
sums=nums[i]+nums[j]+nums[k]
if sums>0:
k-=1
elif sums<0:
j+=1
else:
res.add((nums[i],nums[j],nums[k]))
j+=1
k-=1
return list(res) #這里一個(gè)比較有意思的地方就是旬牲，如何把數(shù)組轉(zhuǎn)化set去重仿粹，然后還能返回list？就是set里以tuple的形式插入引谜，然后直接list它就好
leetcode 16:最接近的三數(shù)之和
這個(gè)問題聽起來也很直接牍陌，給一個(gè)target，找最接近的3個(gè)數(shù)员咽。
因此毒涧，我們需要保存2個(gè)值，一個(gè)是當(dāng)前的和贝室，另一個(gè)是和與目標(biāo)的距離契讲。當(dāng)當(dāng)前和的差值小于距離時(shí)更新，否則看和是大于目標(biāo)還是小于滑频，接著就按照3sum的做法繼續(xù)遍歷捡偏。
具體在實(shí)現(xiàn)的時(shí)候有個(gè)問題，一開始的時(shí)候這個(gè)距離咋辦峡迷？2種方法银伟，1是用初始值-目標(biāo)作為距離，然后遍歷的時(shí)候跳過這種情況绘搞，直接計(jì)算大于目標(biāo)還是小于彤避。2是直接定義一個(gè)最大值，可以是c++的int_max夯辖，Java的Integer.MAX_VALUE琉预，也可以是python的float('inf')。因此實(shí)現(xiàn)如下：
def threesumclosest(nums, target):
nums.sort()
dis=float('inf')
for i in range(len(nums)-2):
j=i+1
k=len(nums)-1
while j<k:
sums=nums[i]+nums[j]+nums[k]
if abs(target-sums)<dis:
s=sums
dis=abs(target-sums)
if sums>target:
k-=1
elif sums<target:
j+=1
elif:
return s
return s
leetcode 18:4sum
其實(shí)可以看出來道理就是那么個(gè)道理蒿褂，2sum的可以用hash圆米，數(shù)量>=3的卒暂，就排個(gè)序，然后乖乖使用雙指針娄帖。這里需要i也祠，j架構(gòu)好循環(huán)次數(shù)，i1 i2 j1 j2來實(shí)際移動块茁，這里i1 j1是外層元素齿坷，就像3sum里的i一樣。代碼也很簡單：
def fourSum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
res=[]
length=len(nums)
for i in range(length-3):
for j in range(length-3):
i1=i
i2=i+1
j1=length-1-j
j2=length-2-j
while i2<j2:
sum_nums=nums[i1]+nums[i2]+nums[j1]+nums[j2]
if sum_nums==target:
res.append([nums[i1],nums[i2],nums[j1],nums[j2]])
j2-=1
i2+=1
elif sum_nums>target:
j2-=1
else:
i2+=1
return list(set([tuple(r) for r in res]))
leetcode 454 :4sum2
我要寫的最后一題了数焊。給定四個(gè)包含整數(shù)的數(shù)組列表 A , B , C , D ,計(jì)算有多少個(gè)元組 (i, j, k, l) 永淌，使得 A[i] + B[j] + C[k] + D[l] = 0。
輸入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
輸出:
2
解釋:
兩個(gè)元組如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
這個(gè)問題也沒啥的佩耳，關(guān)鍵在于4個(gè)數(shù)要滿足的個(gè)數(shù)遂蛀，那么拿出我們的大砍刀：dict。同樣key放具體數(shù)字干厚，value放統(tǒng)計(jì)個(gè)數(shù)李滴。這里，我們可以a+b先放入dict蛮瞄，然后用c+d去match所坯，總體就是O(n2)+O(n2*O(1))，因?yàn)閐ict的in為1：
def fourSumCount(A, B, C, D):
"""
:type A: List[int]
:type B: List[int]
:type C: List[int]
:type D: List[int]
:rtype: int
"""
cnt=0
ab_dict={}
for a in A:
for b in B:
ab_dict[a+b]=ab_dict.get(a+b,0)+1
for c in C:
for d in D:
if -(c+d) in ab_dict:
cnt+=ab_dict[-(c+d)]
return cnt
