代码随想录算法训练营第七天|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

思路

好神奇的思路，因为结果为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:cnt=Counter()forxinnums1:foryinnums2:cnt[x+y]+=1result=0forxinnums3:foryinnums4:result+=cnt[-x-y]returnresult

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

思路

多集比较

代码

classSolution:defcanConstruct(self,ransomNote:str,magazine:str)->bool:ifCounter(ransomNote)<=Counter(magazine):returnTrueelse:returnFalse

15. 三数之和

给你一个整数数组 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]]:n=len(nums)res=[]if(notnumsorn<3):return[]nums.sort()res=[]foriinrange(n):if(nums[i]>0):returnresif(i>0andnums[i]==nums[i-1]):continueL=i+1R=n-1while(L<R):if(nums[i]+nums[L]+nums[R]==0):res.append([nums[i],nums[L],nums[R]])while(L<Randnums[L]==nums[L+1]):L=L+1L=L+1R=R-1elif(nums[i]+nums[L]+nums[R]>0):R=R-1else:L=L+1returnres

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

思路

思路与上一题相同，参考了灵神的优化思路。感觉是一个小学奥数问题。
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=[]n=len(nums)forainrange(n-3):x=nums[a]ifaandx==nums[a-1]:continueifx+nums[a+1]+nums[a+2]+nums[a+3]>target:breakifx+nums[-3]+nums[-2]+nums[-1]<target:continueforbinrange(a+1,n-2):y=nums[b]ifb>a+1andy==nums[b-1]:continueifx+y+nums[b+1]+nums[b+2]>target:breakifx+y+nums[-2]+nums[-1]<target:continuec=b+1d=n-1whilec<d:s=x+y+nums[c]+nums[d]ifs>target:d-=1elifs<target:c+=1else:ans.append([x,y,nums[c],nums[d]])c+=1whilec<dandnums[c]==nums[c-1]:c+=1d-=1whiled>candnums[d]==nums[d+1]:d-=1returnans

总结

没想象中的难，优化时考虑边界问题。