454. 四數(shù)相加 II - 力扣（LeetCode）
解題思路
兩數(shù)之和之不去重plus版
因為用存兩數(shù)之和出現(xiàn)的次數(shù)，所以要用字典院峡；不用數(shù)組是因為int可能會很大兴使，用數(shù)組映射不合適。
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
hashtable1 = {}
for i in range(len(nums1)):
for j in range(len(nums2)):
if nums1[i]+nums2[j] in hashtable1:
hashtable1[nums1[i]+nums2[j]] += 1
else:
hashtable1[nums1[i]+nums2[j]] = 1
count = 0
for i in range(len(nums3)):
for j in range(len(nums4)):
if -(nums3[i]+nums4[j]) in hashtable1:
count += hashtable1[-(nums3[i]+nums4[j])]
return count
- 中間的運算結果可以用中間值存放照激，不然看起來繁瑣
383. 贖金信 - 力扣（LeetCode）
解題思路
magazine存到hashtable鲫惶，ransomNote遍歷，有一個對應的实抡，magazine就-1，沒找到或者找到對應的值為0欢策，就返回False
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
hashtable = {}
for ch in magazine:
if ch in hashtable:
hashtable[ch] += 1
else:
hashtable[ch] = 1
for ch in ransomNote:
if ch not in hashtable or hashtable[ch] == 0:
return False
else:
hashtable[ch] -= 1
return True
15. 三數(shù)之和 - 力扣（LeetCode）
解題思路
- 雙指針吆寨，排序，固定一位踩寇，然后移動左右指針啄清；
- 去重是關鍵，abc都要去重俺孙。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i in range(len(nums)):
if nums[i] > 0:
return result
if i>0 and nums[i] == nums[i-1]: #如果和上一個i對應的值一樣辣卒，跳過，不能是下一個
continue
left = i+1 #
right = len(nums)-1
while left < right:
if (nums[i]+nums[left]+nums[right]) > 0:
right -= 1
elif(nums[i]+nums[left]+nums[right]) < 0:
left += 1
else:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while (left < right) and nums[left] == nums[left-1]:
left += 1 # 不能用if睛榄，不然只能去一個重復的
while (left < right) and nums[right] == nums[right+1]:
right -= 1
return result
18. 四數(shù)之和 - 力扣（LeetCode）
解題思路
三數(shù)之和plus版荣茫，注意去重和剪枝
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
result = []
for k in range(len(nums)):
if target > 0 and nums[k] > target: #一級剪枝
break
if k>0 and nums[k] == nums[k-1]: #一級去重
continue
for i in range(k+1, len(nums)):
if target > 0 and nums[k]+nums[i] > target:#二級剪枝
break
if i>k+1 and nums[i] == nums[i-1]: #二級去重
continue
left = i+1
right = len(nums)-1
while left < right:
sums = nums[k] + nums[i] + nums[left] + nums[right]
if sums > target:
right -= 1
elif sums < target:
left += 1
else:
result.append([nums[k],nums[i],nums[left],nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
return result
