LeetCode 454.四数相加II
题目/视频/文章链接：
454.四数相加||
个人第一时间看法：
考虑到之前做过的两数之和，得用哈希表来解决，只不过对于四个数组的操作有点懵，感觉无从下手，只想到四个for循环暴力解决。
看完代码随想录的想法：
鉴于两数之和的操作，可以将四个数组分成两大组来进行操作，而且这道题不需要考虑重复情况，所以继续用map的结构体。
敲代码时遇到的困难：
满足条件的数组数量应该用前一个大组出现过的次数进行相加，一开始没意识到直接+1了，导致结果数量对应不上。
实际代码：
class Solution(object): def fourSumCount(self, nums1, nums2, nums3, nums4): # use a dict to store the elements in nums1 and nums2 and their sum hashmap = dict() for n1 in nums1: for n2 in nums2: if n1 + n2 in hashmap: hashmap[n1+n2] += 1 else: hashmap[n1+n2] = 1 # if the -(a+b) exists in nums3 and nums4, we shall add the count count = 0 for n3 in nums3: for n4 in nums4: key = - n3 - n4 if key in hashmap: count += hashmap[key] return count
LeetCode 383. 赎金信
题目/视频/文章链接：
383.赎金信
个人第一时间看法：
这和之前做过的字母异位词大同小异，直接用数组的结构来解题即可
看完代码随想录的想法：
这就是一道最基础的哈希表操作题
敲代码时遇到的困难：
没什么难度，能敲出字母异位词的代码，这道题也不在话下
实际代码：
class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: arr = [0] * 26 for x in magazine: # 记录 magazine里各个字符出现次数 arr[ord(x) - ord('a')] += 1 for x in ransomNote: # 在arr里对应的字符个数做--操作 if arr[ord(x) - ord('a')] == 0: # 如果没有出现过直接返回 return False else: arr[ord(x) - ord('a')] -= 1 return True
LeetCode 15. 三数之和
题目/视频/文章链接：
15.三数之和
个人第一时间看法：
懵逼，三个数没办法像之前的四数相加分成两个大组来解题，而且还不能重复，想到set结构体可以不重复，但是三个数该咋用set来遍历呢，挠挠头
看完代码随想录的想法：
既然不需要返回下标，那就可以先进行排序，进而这道题最适方法不是用哈希表，而是用双指针的方法来进行操作，一个从头开始遍历，后两个从两边进行遍历，分清楚什么情况下该移动哪个指针，然后这三个指针都需要进行去重操作，这是个重难点。
敲代码时遇到的困难：
在从头遍历的那个指针进行去重操作时，出现了差错，应该将当前指针的位置与前一个位置进行对比去重，若是对后一个进行对比的话容易漏掉可行结果。
实际代码：
class Solution: def threeSum(self, nums): ans = [] n = len(nums) nums.sort() # 找出a + b + c = 0 # a = nums[i], b = nums[left], c = nums[right] for i in range(n): left = i + 1 right = n - 1 # 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了 if nums[i] > 0: break if i >= 1 and nums[i] == nums[i - 1]: # 去重a continue while left < right: total = nums[i] + nums[left] + nums[right] if total > 0: right -= 1 elif total < 0: left += 1 else: ans.append([nums[i], nums[left], nums[right]]) # 去重逻辑应该放在找到一个三元组之后，对b 和 c去重 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 ans
LeetCode 18. 四数之和
题目/视频/文章链接：
18.四数之和
个人第一时间看法：
基于四数相加和三数之和的思路，既然不需要返回下标，那就可以先排序，进而可以运用双指针，在三个指针的基础上，再在左端加一个指针，前两个为一组，后两个为一组进行操作，挨个遍历从而实现四数之和应该就可以。
看完代码随想录的想法：
只不过这道题给的要求不是0而是target，这样的话在开头判断的时候就有更多的细节了，不只是去重还得剪枝，需要好好琢磨。
敲代码时遇到的困难：
在开头的剪枝操作有点生疏，再就是第二个指针要在第一个指针的基础上进行剪枝去重，得多加熟练才行。
实际代码：
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() n = len(nums) res = [] for i in range(n): if i > 0 and nums[i] == nums[i - 1]: continue # 对nums[i]去重 for k in range(i+1, n): if k > i + 1 and nums[k] == nums[k-1]: continue # 对nums[k]去重 p = k + 1 q = n - 1 while p < q: if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1 elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1 else: res.append([nums[i], nums[k], nums[p], nums[q]]) # 对nums[p]和nums[q]去重 while p < q and nums[p] == nums[p + 1]: p += 1 while p < q and nums[q] == nums[q - 1]: q -= 1 p += 1 q -= 1 return res
今日收获：
今天第一道题也是运用了map的结构进行操作，整体的思路就是看看能不能构成两个组，从而进行哈希表操作解题，第二题就是跟之前的题目进行变式训练而已，熟练操作，第三四题巧妙的运用题目要求，进行排序从而可以使用双指针法进行解题，而且其中的剪枝去重操作格外需要注意细节，仍需多多磨练！今日学习时长2h！
————————————————