代码随想录算法训练营day7 | 454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和

本文主要是介绍代码随想录算法训练营day7 | 454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

454.四数相加II

有下面几种思路：

• 暴力解法，四重循环
• 一个哈希表+三重循环
• 两重循环生成一个哈希表+两重循环

使用两重循环：

class Solution:def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:res = 0num_dict = {}for i in nums1:for j in nums2:if i + j in num_dict:num_dict[i+j] += 1else:num_dict[i + j] = 1for 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] * 26for i in magazine:record[ord(i) - ord(('a'))] += 1for i in ransomNote:if record[ord(i) - ord(('a'))] <= 0:return Falserecord[ord(i) - ord(('a'))] -= 1return 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 resleft = i + 1right = len(nums) - 1while left < right:if nums[i] + nums[left] + nums[right] > 0:right -= 1elif nums[i] + nums[left] + nums[right] < 0:left += 1else:res.append([nums[i], nums[left], nums[right]])# 去重while left < right and nums[right] == nums[right-1]:right -= 1while left < right and nums[left] == nums[left+1]:left += 1left += 1right -= 1return 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 resfor j in range(i+1, len(nums)):if j > i + 1 and nums[j] == nums[j-1]:continueif nums[i] + nums[j] >= 0 and nums[i] + nums[j] > target:breakleft = j + 1right = len(nums) - 1while left < right:if nums[i] + nums[j] + nums[left] + nums[right] > target:right -= 1elif nums[i] + nums[j] + nums[left] + nums[right] < target:left += 1else:res.append([nums[i], nums[j], nums[left], nums[right]])while left < right and nums[right] == nums[right-1]:right -= 1while left < right and nums[left] == nums[left+1]:left += 1left += 1right -= 1return res

这篇关于代码随想录算法训练营day7 | 454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---