454. 四数相加 II - 力扣（LeetCode）
解题思路
两数之和之不去重plus版
因为用存两数之和出现的次数，所以要用字典；不用数组是因为int可能会很大，用数组映射不合适。
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. 三数之和 - 力扣（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. 四数之和 - 力扣（LeetCode）
解题思路
三数之和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
