神奇AC在哪里｜代码随想录算法训练营（DAY7）｜ 454.四数相加I、 383. 赎金信、 15. 三数之和、 18. 四数之和
今日内容：
题目
- 454.四数相加I
- 383. 赎金信
- 15. 三数之和
- 18. 四数之和
454.四数相加I
这个四数相加是有四个数组，四个数组当中各取一个元素使得和为0
该题目和之后的四数之和不同之处在于，四个数是来自四个不同的数组。所以不需要考虑重复的问题。
那么解法如下：采用哈希的方法，将前两个数组的元素和为一组，存储在一个字典当中，key为两个元素的和，value为这个和出现的次数。然后剩下两个元素的元素和为另一个组，目的是找这剩下的元素和等于之前的元素和的相反数，成功找到的则满足题意。代码如下：
这里hashmap.get(n + m, 0)是指提取n+m这个位置的哈希value的值，如果这个key之前没有存储过，则默认返回0.
class Solution: def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int: hashmap = dict() for n in nums1: for m in nums2: hashmap[n + m] = hashmap.get(n + m, 0) + 1 cnt = 0 for n in nums3: for m in nums4: target = -(n + m) if target in hashmap: # cnt += hashmap[target] cnt += hashmap.get(target) return cnt 383. 赎金信
这个题目没有什么需要特别注意的点，唯一需要关注的是：magazine 中的每个字符只能在 ransomNote 中使用一次。也就是ransomNote中哪怕是出现重复元素，重复几次，magazine中必须有几次。（绑匪绑架通过裁剪报纸字母生成赎金信，报纸中裁剪下来的字母只能在赎金信中用一次，分身乏术没法复用）。
class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: hashmap = dict() for strb in magazine: hashmap[strb] = hashmap.get(strb, 0) + 1 for stra in ransomNote: if stra not in hashmap or hashmap[stra] <= 0: return False hashmap[stra] = hashmap.get(stra, 0) - 1 return True 15. 三数之和
该题目比较复杂，哈希算法很难进行所有情况条件的判定和重复元素的排除，所以不采用哈希法，二是采用排序之后双指针的策略。
要点：
- 数组需要排序，因为我们要采用双指针的方法，必须让数据有序才可以进行值的定性分析。
- 注意重复元素的判断排除。比如：
if i > 0 and nums[i] == nums[i - 1],这个是判断当前位置和前一个位置是否有重复的元素。因为如果重复了的话也就意味着这两个重复元素已经在一个元组里用过了，所以i要continue。同时还需要注意的是不能写成nums[i] == nums[i+1]的形式，因为这种形式是判断当前元素和下一个元素是否重复，相当于把未处理的空间给处理了。 - while循环当中，如果存在了这么一组数满足题意，那么在将其添加到结果之后，如果left和right指针往中间方向有相同的元素的话，要跳过，即
while left < right and nums[left] == nums[left + 1]和while left < right and nums[right] == nums[right - 1]，防止出现重复的元组。
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]: continue left = i + 1 right = len(nums) - 1 while left < right: tempsum = nums[i] + nums[left] + nums[right] if tempsum > 0: right -= 1 elif tempsum < 0: left += 1 else: res = [nums[i], nums[left], nums[right]] result.append(res) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return result 18. 四数之和
基本原理和三数之和相同，多了一层for循环，同时加了对和的限制，不是和为0而是和等于给定值。
需要注意几点：
- target可能为正也可能为负
- 数组经过排序之后，按照从左到右依次递增。但是！并不意味着从左向右加和会递增！（如-5，-4，-3，-2；越加越小）
- 最后的debug好久的问题，最后的else后的内容是包括左右指针向中间越过相同元素的。注意缩进和理解
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: result = [] nums.sort() for i in range(len(nums)): if nums[i] > target and nums[i] > 0: return result if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, len(nums)): if nums[i] + nums[j] > target and nums[i] > 0: return result if j > i + 1 and nums[j] == nums[j - 1]: continue left = j + 1 right = len(nums) - 1 while left < right: temp = nums[i] + nums[j] + nums[left] + nums[right] if temp > target: right -= 1 elif temp < target: left += 1 else: result.append([nums[i], nums[j], nums[left], nums[right]]) while left < right and nums[left] == nums[left + 1]: left += 1 while left < right and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return result 总结
哈希这一部分原理方法还是不算难理解，就是哈希表存法写法比较多，注意语言的熟悉和应用。最后两双指针求数字和的方法多看多练习。
