当前位置：首页 > news >正文

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

news 2026/4/5 22:49:18

454. 四数相加 II

题目描述

解题思路

易错点

复杂度分析

383. 赎金信

题目描述

解题思路

复杂度分析

15. 三数之和

题目描述

解题思路

复杂度分析

18. 四数之和

题目描述

解题思路

易错点

复杂度分析

哈希表总结

454. 四数相加 II

题目描述

给你四个整数数组nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i, j, k, l)能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

解题思路

将nums3和nums4移到等式右边去，这样1+2 = - 3 - 4，记录1+2的和（此题找不同的下标，所以尽管元素可能相同但是下标不一样还是不同的组合），再计算-3-4看是否和他相等
这样问题就转换成了判断-3-4是否在1+2的集合中存在，由此此题使用哈希

使用什么数据结构呢？

数组：由题四个数组的取值范围很大，存放到数组里会造成极大的空间浪费
集合：本题是用下标来进行统计，不能去重
字典（映射）：综上所述，该数据结构很合适

class Solution(object): def fourSumCount(self, nums1, nums2, nums3, nums4): cnt = defaultdict(int) for n in nums1: for m in nums2: cnt[n + m] += 1 ans = 0 for n in nums3: for m in nums4: ans += cnt[-n - m] if - n - m in cnt else 0 return ans

易错点

计算ans时寻找的是cnt中-n-m的值，而不是m+n

复杂度分析

时间复杂度
- 有两个for循环，且数组长度都相同，O(n^2)
空间复杂度
- 主要是哈希表，最多存储了n * n组数据，O(n^2)

383. 赎金信

题目描述

给你两个字符串：ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。
如果可以，返回true；否则返回false。
magazine中的每个字符只能在ransomNote中使用一次。

解题思路

同242. 有效的字母异位词

class Solution(object): def canConstruct(self, ransomNote, magazine): cnt = defaultdict(int) for r in ransomNote: cnt[r] += 1 for m in magazine: if m in cnt: cnt[m] -= 1 for c in cnt: if cnt[c] > 0: return False return True

class Solution(object): def canConstruct(self, ransomNote, magazine): return not Counter(ransomNote) - Counter(magazine)

class Solution(object): def canConstruct(self, ransomNote, magazine): return all(ransomNote.count(c) <= magazine.count(c) for c in set(ransomNote))

复杂度分析

时间复杂度
- 和字符串长度有关，O(m+n)
空间复杂度
- 字母只有26个，O(1)

15. 三数之和

题目描述

给你一个整数数组nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组。
注意：答案中不可以包含重复的三元组。

解题思路

三数之和，依旧可以转化为两数之和是否存在于-a中，但是由于哈希适合处理寻找元素的存在性，对于去重十分的繁琐
由此，来使用双指针计算两数的和并与第一个数进行比较就是一个新的思路
但是，在做题过程中，去重是这个题目最大的难题
由此，我们可以将去重操作切割为三部分
- 第一部分：首元素的去重，那么我们是用nums[i] == nums[i-1]还是用nums[i] == nums[i + 1]来进行判断呢？
  - 举个栗子，符合题意的数组为[-1,-1,2,4]，此时i位于首地址，left指针指向-1，right指针指向2，如果使用后者，那么left指向2，right指向4，就跳过了一种可能情况，故选前者
- 第二部分：left（第二个元素）的去重，只需要在找到目标集合后，对left+1即可
  - 举个栗子：此时数组为[-1,-1,-1,2]，left指向第二个-1，right指向2，只需要对left+1即可跳过相同元素的情况
- 第三部分：right（第三个元素）的去重，同上

class Solution(object): def threeSum(self, nums): ans = [] nums.sort() for i in range(len(nums)): #nums[0]为正数，后面全为正数，相加不可能等于0 if nums[i] > 0: break if i > 0 and nums[i] == nums[i - 1]: continue left = i + 1 right = len(nums) - 1 while right > left: if nums[right] + nums[left] > -nums[i]: right -= 1 elif nums[right] + nums[left] < -nums[i]: left += 1 else: ans.append([nums[i],nums[left],nums[right]]) while right > left and nums[left] == nums[left + 1]: left += 1 while right > left and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return ans

复杂度分析

时间复杂度
- 排序：O(nlogn)
- 外层循环O(n) +内层双指针O(n)--->O(n^2)
- 总复杂度：O(n^2)
空间复杂度
- sort原地排序，空间复杂度为O(logn)
- 总复杂度：O(logn)

18. 四数之和

题目描述

给你一个由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
你可以按任意顺序返回答案。

解题思路

就是三数之和外面嵌套一层来增加一个数

class Solution(object): def fourSum(self, nums, target): ans=[] nums.sort() for i in range(len(nums)): if nums[i] > target and nums[i] > 0 and target > 0: break if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1,len(nums)): if nums[j] + nums[i] > target and target > 0: break if j > i + 1 and nums[j] == nums[j - 1]: continue left = j + 1 right = len(nums) - 1 while right > left: sum_ = nums[i] + nums[j] + nums[left] + nums[right] if sum_ > target: right -= 1 elif sum_ < target: left += 1 else: ans.append([nums[i],nums[j],nums[left],nums[right]]) while right > left and nums[left] == nums[left + 1]: left += 1 while right > left and nums[right] == nums[right - 1]: right -= 1 left += 1 right -= 1 return ans