题目简介
454: 四数相加II https://leetcode.cn/problems/4sum-ii/description/
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
383: 赎金信 https://leetcode.cn/problems/ransom-note/description/
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
15: 三数之和 https://leetcode.cn/problems/3sum/description/
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
18: 四数之和 https://leetcode.cn/problems/4sum/description/
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
初见思路
454: 采用哈希表+加和的方式是最直观的方式
from collections import defaultdict
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
hash_map = defaultdict()
for n1 in nums1:
for n2 in nums2:
hash_map[n1+n2] = hash_map.get(n1+n2,0) + 1
cnt = 0
for n4 in nums4:
for n3 in nums3:
cnt += hash_map.get(-n4-n3,0)
return cnt
- 这道题就是简单的比较字典里记录的字母的数量，没有啥好讲的。
from collections import OrderedDict
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
dict_1,dict_2 = OrderedDict(),OrderedDict()
for ch_1 in ransomNote:
dict_1[ch_1] = dict_1.get(ch_1,0) + 1
for ch_2 in magazine:
dict_2[ch_2] = dict_2.get(ch_2,0) + 1
for k,v in dict_1.items():
if v > dict_2.get(k,0):
return False
return True
- 以前的题解，注意简化该问题两个点：排序+去重
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans, i = [],0
for i in range(len(nums)-2):
if nums[i] > 0: break # 三数和为0，那么如果排序后首位元素为正，该问题无解
if i > 0 and nums[i] == nums[i-1]: continue # 过滤重复元素
j,k = i + 1,len(nums) - 1
while j < k:
triple_sum = nums[i] + nums[j] + nums[k]
if triple_sum < 0:
j += 1
while j < k and nums[j] == nums[j - 1]: j += 1 # 过滤重复元素
elif triple_sum > 0:
k -= 1
while j < k and nums[k] == nums[k + 1]: k -= 1 # 过滤重复元素
else:
ans.append([nums[i],nums[j],nums[k]])
j += 1
k -= 1
while j < k and nums[j] == nums[j - 1]: j += 1 # 过滤重复元素
while j < k and nums[k] == nums[k + 1]: k -= 1 # 过滤重复元素
return ans
第二个核心在与固定第一个元素，后续两个元素采取窗口缩容的方式逐渐向后搜索，直到遍历完整个数组。
- 这题相当于是15三数之和的升级版，在三数之和基础上固定第一个元素的逻辑即可，可以AC但是比较慢，暂时没想到哈希表的解法
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
ans = []
for a in range(len(nums)-3):
if nums[a] > target and nums[a] > 0 and target > 0:
break
if a > 0 and nums[a] == nums[a - 1]: continue
for b in range(a+1,len(nums)-2): # repeat what we did in triple sum
if nums[b] + nums[a] > target and target > 0:
break
if b > a+ 1 and nums[b] == nums[b - 1]:
continue
c,d = b + 1, len(nums) - 1
while c < d:
four_sum = nums[a] + nums[b] + nums[c] + nums[d]
if four_sum == target:
ans.append([nums[a],nums[b],nums[c],nums[d]])
c += 1
d -= 1
while c< d and nums[c] == nums[c-1]: c += 1
while c< d and nums[d] == nums[d+1]: d -= 1
elif four_sum < target:
c += 1
while c< d and nums[c] == nums[c-1]: c += 1
else:
d -= 1
while c< d and nums[d] == nums[d+1]: d -= 1
return ans
复盘思路
https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html
https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html
https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html
https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html
重点难点
- 哈希集的基本操作要熟悉，多使用各种方法实现哈希集
- N数之和的问题可以用双指针杀，但是并不是最优的解法，而且微操很多，剪枝的条件比较绕，要想明白为什么这样剪。
今日收获
见上方重点难点，后续复习了随想录解法再补充。
