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

非原创搬运记录解题方法学习思路一同进步Day7 第三章 哈希表part02备忘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思路好神奇的思路因为结果为0所以四项中两项到等式的另一边。a b c d 0→ a b - (c d)代码classSolution:deffourSumCount(self,nums1:List[int],nums2:List[int],nums3:List[int],nums4:List[int])-int:cntCounter()forxinnums1:foryinnums2:cnt[xy]1result0forxinnums3:foryinnums4:resultcnt[-x-y]returnresult383. 赎金信给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以返回 true 否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。思路多集比较代码classSolution:defcanConstruct(self,ransomNote:str,magazine:str)-bool:ifCounter(ransomNote)Counter(magazine):returnTrueelse:returnFalse15. 三数之和给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。思路没什么技巧可言传统做法。先排序因为需要满足三数之和为0所以第一个数0或者数组长度不足3就可以排除了。接着固定第一个值后利用双指针找到满足和为0的index再排除重复值。代码classSolution:defthreeSum(self,nums:list[int])-list[list[int]]:nlen(nums)res[]if(notnumsorn3):return[]nums.sort()res[]foriinrange(n):if(nums[i]0):returnresif(i0andnums[i]nums[i-1]):continueLi1Rn-1while(LR):if(nums[i]nums[L]nums[R]0):res.append([nums[i],nums[L],nums[R]])while(LRandnums[L]nums[L1]):LL1LL1RR-1elif(nums[i]nums[L]nums[R]0):RR-1else:LL1returnres18. 四数之和给你一个由 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你可以按 任意顺序 返回答案 。思路思路与上一题相同参考了灵神的优化思路。感觉是一个小学奥数问题。https://leetcode.cn/problems/4sum/solutions/2344514/ji-zhi-you-hua-ji-yu-san-shu-zhi-he-de-z-1f0b代码classSolution:deffourSum(self,nums:List[int],target:int)-List[List[int]]:nums.sort()ans[]nlen(nums)forainrange(n-3):xnums[a]ifaandxnums[a-1]:continueifxnums[a1]nums[a2]nums[a3]target:breakifxnums[-3]nums[-2]nums[-1]target:continueforbinrange(a1,n-2):ynums[b]ifba1andynums[b-1]:continueifxynums[b1]nums[b2]target:breakifxynums[-2]nums[-1]target:continuecb1dn-1whilecd:sxynums[c]nums[d]ifstarget:d-1elifstarget:c1else:ans.append([x,y,nums[c],nums[d]])c1whilecdandnums[c]nums[c-1]:c1d-1whiledcandnums[d]nums[d1]:d-1returnans总结没想象中的难优化时考虑边界问题。