454.四數(shù)相加II
題目鏈接：
454. 四數(shù)相加 II - 力扣（Leetcode）
給定四個(gè)包含整數(shù)的數(shù)組列表 A , B , C , D ,計(jì)算有多少個(gè)元組 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
為了使問題簡單化，所有的 A, B, C, D 具有相同的長度 N，且 0 ≤ N ≤ 500 。所有整數(shù)的范圍在 -2^28 到 2^28 - 1 之間，最終結(jié)果不會超過 2^31 - 1 。
例如:
輸入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
輸出:2
收獲的點(diǎn)
1）Counter函數(shù)又用上了
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
#將四個(gè)數(shù)組轉(zhuǎn)化為索引相同的字典，字典的key為數(shù)組的索引，字典的value為四個(gè)數(shù)組對應(yīng)的值的列表（或元組），通過查找索引對應(yīng)的不同數(shù)值判斷有多少個(gè)元組
hashtable = Counter(u+v for u in nums1 for v in nums2) #將第一個(gè)數(shù)組和第二個(gè)數(shù)組的和加起來
ans = 0
for i in nums3:
for j in nums4:
if -(i+j) in hashtable:
ans +=hashtable[-i-j] #如果數(shù)組3和數(shù)組4存在數(shù)組1和數(shù)組2加和為0的記一次
return ans
- 贖金信
題目鏈接：
383. 贖金信 - 力扣（Leetcode）
給你兩個(gè)字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構(gòu)成。
如果可以，返回 true ；否則返回 false 。
magazine 中的每個(gè)字符只能在 ransomNote 中使用一次。
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
#判斷ransomNote中的元素都在magazine里面感覺就可以了，即前者是后者的子集
a = Counter(ransomNote)
b = Counter(magazine)
for x in ransomNote:
value = b.get(x)
value2 = a.get(x)
if value is None or int(value) < int(value2):
return False
return True
一道基本自己做出來的題，但是發(fā)現(xiàn)還有更簡潔的解法：
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
c1 = collections.Counter(ransomNote)
c2 = collections.Counter(magazine)
x = c1 - c2
#x只保留值大于0的符號，當(dāng)c1里面的符號個(gè)數(shù)小于c2時(shí)，不會被保留
#所以x只保留下了，magazine不能表達(dá)的
if(len(x)==0):
return True
else:
return False
三數(shù)之和
題目鏈接：
15. 三數(shù)之和 - 力扣（Leetcode）
給你一個(gè)整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時(shí)還滿足 nums[i] + nums[j] + nums[k] == 0 。請
你返回所有和為 0 且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
收獲的點(diǎn)：
1）對于重復(fù)值的去除，第一個(gè)元素去重，nums[i]==nums[i-1]的判斷；
2）第二個(gè)元素和第三個(gè)元素在while里面的去重，非常值得回味；
3）索引遍歷+雙指針的思路。
完整代碼：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
res = []
if nums is None or n < 3:
return []
for i in range(n):
if nums[i] > 0:
return res
if i > 0 and nums[i] == nums[i-1]: #去重第一個(gè)元素
continue
L = i + 1
R = n - 1
while L < R :
if nums[i] + nums[L] + nums[R] ==0:
res.append([nums[i],nums[L], nums[R]]) #這里面的去重非常巧妙，這兩個(gè)while的設(shè)置
while L < R and nums[L] == nums[L+1]: #去重第二個(gè)元素
L +=1
while L < R and nums[R] == nums[R-1]:#去重第三個(gè)元素
R -=1
L +=1
R -=1
elif nums[i] + nums[L] + nums[R] < 0 :
L +=1
else:
R -=1
return res
第18題. 四數(shù)之和
題目鏈接：
18. 四數(shù)之和 - 力扣（Leetcode）
給你一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組 nums ，和一個(gè)目標(biāo)值 target 。請你找出并返回滿足下述全部條件且不重復(fù)的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個(gè)四元組元素一一對應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]: continue # 對nums[i]去重
for k in range(i+1, n):
if k > i + 1 and nums[k] == nums[k-1]: continue # 對nums[k]去重
p = k + 1
q = n - 1
while p < q:
if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
else:
res.append([nums[i], nums[k], nums[p], nums[q]])
# 對nums[p]和nums[q]去重
while p < q and nums[p] == nums[p + 1]: p += 1
while p < q and nums[q] == nums[q - 1]: q -= 1
p += 1
q -= 1
return res
兩層循環(huán)+雙指針
