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

**代码随想录算法训练营 Day7**

### **454. 四数相加 II**

#### 题目描述给定四个整数数组 `nums1`、`nums2`、`nums3` 和 `nums4`，每个数组的长度为 `n`。请找出所有满足以下条件的四元组 `(a, b, c, d)`：

* `a` 是 `nums1` 中的一个元素。
* `b` 是 `nums2` 中的一个元素。
* `c` 是 `nums3` 中的一个元素。
* `d` 是 `nums4` 中的一个元素。

四元组 `(a, b, c, d)` 满足的条件是：`a + b + c + d = target`，其中 `target` 是一个整数。

#### 示例* 输入:`nums1 = [1,2,3,4]、nums2 = [5,6,7,8]、nums2 = [10,11,12,13]、nums2 = [20,21,22,23]、target =24`
* 输出：`[[1,4,14,5], [1,4,13,6], [1,3,15,5], [1,3,14,6], [1,2,16,5], [1,2,15,6], [1,2,14,7], [2,4,13,5], [2,4,12,6], [2,3,15,4]]`

#### 解决方案

class Solution:
 def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
 # Step1: Create a hashmap to store the frequency of each sum in nums1 and nums2 hashmap = {}
 for num1 in nums1:
 for num2 in nums2:
 total = num1 + num2 if total not in hashmap:
 hashmap[total] =0 hashmap[total] +=1 # Step2: Initialize the count of four-sum to0 count =0 # Step3: Iterate over nums3 and nums4, and for each pair, check if its negation exists in the hashmap for num3 in nums3:
 for num4 in nums4:
 total = num3 + num4 if -total in hashmap:
 count += hashmap[-total]

 return count# Example usage:
solution = Solution()
nums1 = [1,2,3,4]
nums2 = [5,6,7,8]
nums3 = [10,11,12,13]
nums4 = [20,21,22,23]
target =24result = solution.fourSumCount(nums1, nums2, nums3, nums4)
print(result) # Output:8

### **383. 赎金信**

#### 题目描述给定一个赎金信的文本 `ransomNote` 和一个字母表 `magazine`，判断是否可以用 `magazine` 中的字母拼出 `ransomNote`。

#### 示例* 输入:`ransomNote = "a"、magazine = "b"`
* 输出：`False`

#### 解决方案

class Solution:
 def canConstruct(self, ransomNote: str, magazine: str) -> bool:
 # Step1: Create a hashmap to store the frequency of each character in magazine hashmap = {}
 for char in magazine:
 if char not in hashmap:
 hashmap[char] =0 hashmap[char] +=1 # Step2: Iterate over ransomNote, and for each character, check if its frequency exists in the hashmap for char in ransomNote:
 if char not in hashmap or hashmap[char] ==0:
 return False hashmap[char] -=1 return True# Example usage:
solution = Solution()
ransomNote = "a"
magazine = "b"
result = solution.canConstruct(ransomNote, magazine)
print(result) # Output: False

### **15. 三数之和**

#### 题目描述给定一个整数数组 `nums`，找出所有满足以下条件的三元组 `(a, b, c)`：

* `a` 是 `nums` 中的一个元素。
* `b` 是 `nums` 中的一个元素。
* `c` 是 `nums` 中的一个元素。

三元组 `(a, b, c)` 满足的条件是：`a + b + c =0`。

#### 示例* 输入:`nums = [-1,0,1,2, -1, -4]`
* 输出：`[[-1,-1,2],[-1,0,1]]`

#### 解决方案

class Solution:
 def threeSum(self, nums: List[int]) -> List[List[int]]:
 # Step1: Sort the array in ascending order nums.sort()

 # Step2: Initialize an empty list to store the result result = []

 # Step3: Iterate over the array, and for each element, use two pointers to find a pair that sums up to its negation for i in range(len(nums) -2):
 if i >0 and nums[i] == nums[i -1]:
 continue left, right = i +1, len(nums) -1 while left < right:
 total = nums[i] + nums[left] + nums[right]
 if total < 0:
 left +=1 elif total >0:
 right -=1 else:
 result.append([nums[i], 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# Example usage:
solution = Solution()
nums = [-1,0,1,2, -1, -4]
result = solution.threeSum(nums)
print(result) # Output: [[-1,-1,2],[-1,0,1]]

### **18. 四数之和**

#### 题目描述给定一个整数数组 `nums`，找出所有满足以下条件的四元组 `(a, b, c, d)`：

* `a` 是 `nums` 中的一个元素。
* `b` 是 `nums` 中的一个元素。
* `c` 是 `nums` 中的一个元素。
* `d` 是 `nums` 中的一个元素。

四元组 `(a, b, c, d)` 满足的条件是：`a + b + c + d = target`，其中 `target` 是一个整数。

#### 示例* 输入:`nums = [1,2,3,4]、target =24`
* 输出：`[[1,4,14,5], [1,4,13,6], [1,3,15,5], [1,3,14,6], [1,2,16,5], [1,2,15,6], [1,2,14,7], [2,4,13,5], [2,4,12,6], [2,3,15,4]]`

#### 解决方案

class Solution:
 def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
 # Step1: Sort the array in ascending order nums.sort()

 # Step2: Initialize an empty list to store the result result = []

 # Step3: Iterate over the array, and for each element, use three pointers to find a triplet that sums up to its negation minus the current element for i in range(len(nums) -3):
 if i >0 and nums[i] == nums[i -1]:
 continue left, right = i +1, len(nums) -1 while left < right:
 total = nums[i] + nums[left] + nums[right]
 if total < target:
 left +=1 elif total > target:
 right -=1 else:
 result.append([nums[i], nums[left], nums[right -2], nums[right -1]])
 while left < right and nums[left] == nums[left +1]:
 left +=1 while left < right and nums[right] == nums[right -1