這里寫(xiě)幾個(gè)sum問(wèn)題的總結(jié)。
首先是
leetcode 1：two sum
解法很簡(jiǎn)單，就是哈希表。哈希表的查找速度是O(1)，當(dāng)然是平均時(shí)間，最差是O(n)，對(duì)應(yīng)全部沖突。當(dāng)然，以python的dict為例，dict是會(huì)擴(kuò)容的，擴(kuò)容的時(shí)候會(huì)rehash。所以這個(gè)時(shí)候的內(nèi)部也會(huì)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è)問(wèn)題有意思在，已經(jīng)排好序了，那么哈希似乎顯得不夠靈活了，我們考慮，可以用一種叫做“雙指針”的東西，雙指針應(yīng)用及其廣，最牛逼的用法就是鏈表求環(huán)，堪稱(chēng)天人。不過(guò)這里不說(shuō)那個(gè)，我們認(rèn)為，首先把一個(gè)指針?lè)旁陬^部，另一個(gè)指向尾部，然后如果大了就尾指針向內(nèi)，小了就頭指針向后。也很簡(jiǎn)單，如下：
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開(kāi)始
elif sums > target:
j -= 1
else:
i += 1
leetcode 653:wo sum, Input is a BST
這道題是給的是一顆二叉樹(shù)，我們要找到target，否則返回False。做法就是dfs一棵樹(shù)，而內(nèi)部這個(gè)查找的過(guò)程和two sum是一樣的，為了快速，我們用一個(gè)set（set和dict一樣都是hashable，查找速度O(1)），這個(gè)set里保存target-root.val的值，因此便利的時(shí)候只要val in s，就說(shuō)明找到了。同時(shí)，這樣保存還有一個(gè)好處，如果真的只能保存一個(gè)值，那隨著我們遍歷，我們會(huì)不?；厮荩闊┑囊还P。而如果我們把候選都放到set里，每次只需看看需要的在不在就行了。第一題之所以用dict，是因?yàn)樾枰瑫r(shí)保存標(biāo)號(hào)和數(shù)值，而這個(gè)只需要標(biāo)號(hà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)面試官，我一定會(huì)考這道題。這道題的時(shí)間要求是O(lg(n))，也就是說(shuō)，不能有一般直接查找的操作。雖然很多提交時(shí)間很短，但是都有找到點(diǎn)后兩側(cè)遍歷的操作，這種操作在大規(guī)模上必然會(huì)爆，能ac僅僅是lc的case太少了。
要我來(lái)解，必然只能純查找，也就是，找到起點(diǎn)，找到終點(diǎn)。binary search的模板已經(jīng)很清晰了，看起來(lái)大了就減end，小了就加start的操作似乎也不能改變，故能變的也就是==的情況了
假設(shè)尋找第一個(gè)，那么當(dāng)mid<target時(shí)，我們正常start右移，mid+1。如果大于，那么end左移，mid-1，可是如果==？這里不會(huì)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è)之和，代碼就變得很簡(jiǎn)單，也可以把兩個(gè)融合到一起，但是沒(méi)有必要。
leetcode 15:三數(shù)之和
這個(gè)題其實(shí)也是雙指針，不過(guò)因?yàn)橛?個(gè)數(shù)，所以需要第3個(gè)指針來(lái)控制遍歷，其余的和已排序的2sum一樣。之所以一樣，是因?yàn)閷?duì)于O(n^2)的復(fù)雜度而言，排序的O(nlgn)不算太過(guò)分：
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è)問(wèn)題聽(tīng)起來(lái)也很直接，給一個(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è)問(wèn)題，一開(kāi)始的時(shí)候這個(gè)距離咋辦？2種方法，1是用初始值-目標(biāo)作為距離，然后遍歷的時(shí)候跳過(guò)這種情況，直接計(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í)可以看出來(lái)道理就是那么個(gè)道理，2sum的可以用hash，數(shù)量>=3的，就排個(gè)序，然后乖乖使用雙指針。這里需要i，j架構(gòu)好循環(huán)次數(shù)，i1 i2 j1 j2來(lái)實(shí)際移動(dòng)，這里i1 j1是外層元素，就像3sum里的i一樣。代碼也很簡(jiǎn)單：
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
我要寫(xiě)的最后一題了。給定四個(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è)問(wèn)題也沒(méi)啥的，關(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
