目录454. 四数相加 II题目描述解题思路易错点复杂度分析383. 赎金信题目描述解题思路复杂度分析15. 三数之和题目描述解题思路复杂度分析18. 四数之和题目描述解题思路易错点复杂度分析哈希表总结454. 四数相加 II题目描述给你四个整数数组nums1、nums2、nums3和nums4数组长度都是n请你计算有多少个元组(i, j, k, l)能满足0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0解题思路将nums3和nums4移到等式右边去这样12 - 3 - 4记录12的和此题找不同的下标所以尽管元素可能相同但是下标不一样还是不同的组合再计算-3-4看是否和他相等这样问题就转换成了判断-3-4是否在12的集合中存在由此此题使用哈希使用什么数据结构呢数组由题四个数组的取值范围很大存放到数组里会造成极大的空间浪费集合本题是用下标来进行统计不能去重字典映射综上所述该数据结构很合适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的值而不是mn复杂度分析时间复杂度有两个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 Trueclass 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(mn)空间复杂度字母只有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指针指向-1right指针指向2如果使用后者那么left指向2right指向4就跳过了一种可能情况故选前者第二部分left第二个元素的去重只需要在找到目标集合后对left1即可举个栗子此时数组为[-1,-1,-1,2]left指向第二个-1right指向2只需要对left1即可跳过相同元素的情况第三部分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 na、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易错点此题的目标值是target而不是0在进行剪枝操作时只有当数组内的数都为正数并且target0才能去剪枝举个栗子数组为[-2,-1,0,0,1,2],target -3时剪枝操作时-2-3就会跳过这个情况因为数相加并不一定是越加越大为负数的时候也会越加越小复杂度分析时间复杂度两层外循环O(n^2)双指针O(n)---O(n^3)排序O(nlogn)空间复杂度sort原地排序空间复杂度为O(logn)总空间复杂度O(logn)哈希表总结哈希表是用来快速判断一个元素是否在集合里哈希表的数据结构数组setmap各自适用的场景
代码随想录算法训练营第七天|454、两数相加II 383、赎金信 15、三数之和 18、四数之和
目录454. 四数相加 II题目描述解题思路易错点复杂度分析383. 赎金信题目描述解题思路复杂度分析15. 三数之和题目描述解题思路复杂度分析18. 四数之和题目描述解题思路易错点复杂度分析哈希表总结454. 四数相加 II题目描述给你四个整数数组nums1、nums2、nums3和nums4数组长度都是n请你计算有多少个元组(i, j, k, l)能满足0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0解题思路将nums3和nums4移到等式右边去这样12 - 3 - 4记录12的和此题找不同的下标所以尽管元素可能相同但是下标不一样还是不同的组合再计算-3-4看是否和他相等这样问题就转换成了判断-3-4是否在12的集合中存在由此此题使用哈希使用什么数据结构呢数组由题四个数组的取值范围很大存放到数组里会造成极大的空间浪费集合本题是用下标来进行统计不能去重字典映射综上所述该数据结构很合适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的值而不是mn复杂度分析时间复杂度有两个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 Trueclass 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(mn)空间复杂度字母只有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指针指向-1right指针指向2如果使用后者那么left指向2right指向4就跳过了一种可能情况故选前者第二部分left第二个元素的去重只需要在找到目标集合后对left1即可举个栗子此时数组为[-1,-1,-1,2]left指向第二个-1right指向2只需要对left1即可跳过相同元素的情况第三部分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 na、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易错点此题的目标值是target而不是0在进行剪枝操作时只有当数组内的数都为正数并且target0才能去剪枝举个栗子数组为[-2,-1,0,0,1,2],target -3时剪枝操作时-2-3就会跳过这个情况因为数相加并不一定是越加越大为负数的时候也会越加越小复杂度分析时间复杂度两层外循环O(n^2)双指针O(n)---O(n^3)排序O(nlogn)空间复杂度sort原地排序空间复杂度为O(logn)总空间复杂度O(logn)哈希表总结哈希表是用来快速判断一个元素是否在集合里哈希表的数据结构数组setmap各自适用的场景
