454.四数相加II
有下面几种思路:
- 暴力解法,四重循环
- 一个哈希表+三重循环
- 两重循环生成一个哈希表+两重循环
使用两重循环:
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
res = 0
num_dict = {}
for i in nums1:
for j in nums2:
if i + j in num_dict:
num_dict[i+j] += 1
else:
num_dict[i + j] = 1
for i in nums3:
for j in nums4:
if 0 - i - j in num_dict:
res += num_dict[0-i-j]
return res
一个优化点
if i + j in num_dict:
num_dict[i+j] += 1
else:
num_dict[i + j] = 1
可改写为
num_dict[i+j] = num_dict.get(i+j, 0) + 1
383. 赎金信
本题只由小写英文字母组成,因此可以声明一个26位的数组
先遍历杂志字符串,得到每个字符的个数;然后遍历赎金信字符串,减去相应的字符个数,如果字符个数小于零了,说明不能构成
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
record = [0] * 26
for i in magazine:
record[ord(i) - ord(('a'))] += 1
for i in ransomNote:
if record[ord(i) - ord(('a'))] <= 0:
return False
record[ord(i) - ord(('a'))] -= 1
return True
15. 三数之和
第一反应是哈希表加两重循环,得到结果后需要去重,而去重过程较复杂,因此使用双指针法
使用双指针法需要先排序,然后在一个循环中使用双指针
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums)):
# 去重
if i > 0 and nums[i] == nums[i-1]:
continue
# 剪枝
if nums[i] > 0:
return res
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:
res.append([nums[i], nums[left], nums[right]])
# 去重
while left < right and nums[right] == nums[right-1]:
right -= 1
while left < right and nums[left] == nums[left+1]:
left += 1
left += 1
right -= 1
return res
18. 四数之和
使用双指针,先排序,然后在两重循环中使用双指针
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums)):
# 去重
if i > 0 and nums[i] == nums[i-1]:
continue
# 剪枝
if nums[i] >= 0 and nums[i] > target:
return res
for j in range(i+1, len(nums)):
if j > i + 1 and nums[j] == nums[j-1]:
continue
if nums[i] + nums[j] >= 0 and nums[i] + nums[j] > target:
break
left = j + 1
right = len(nums) - 1
while left < right:
if nums[i] + nums[j] + nums[left] + nums[right] > target:
right -= 1
elif nums[i] + nums[j] + nums[left] + nums[right] < target:
left += 1
else:
res.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[right] == nums[right-1]:
right -= 1
while left < right and nums[left] == nums[left+1]:
left += 1
left += 1
right -= 1
return res