代码随想录算法训练营第六天 | 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] 0classSolution:deffourSumCount(self,nums1:List[int],nums2:List[int],nums3:List[int],nums4:List[int])-int:hashmapdict()foriinnums1:forjinnums2:ifijinhashmap:hashmap[ij]1else:hashmap[ij]1count0foriinnums3:forjinnums4:key-i-jifkeyinhashmap:counthashmap[key]returncount学习心得先定义一个hashmap字典。将nums1nums2的值与出现次数统计到hashmap里之后再看-nums3-nums4的值在不在hashmap在的话则count更新加上刚刚统计的nums1nums2的出现次数383. 赎金信给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以返回 true 否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。classSolution:defcanConstruct(self,ransomNote:str,magazine:str)-bool:shuzu[0]*26foriinstr(magazine):shuzu[ord(i)-ord(a)]1forjinstr(ransomNote):shuzu[ord(j)-ord(a)]-1foriinrange(len(shuzu)):ifshuzu[i]0:returnFalsereturnTrue学习心得定义一个26大小的的0值数组。先统计magazine里面各单词出现次数。再统计ransomNote里的每个字符出现则在数组相应单词位置次数-1。最后看数组里面有没有负数有的话说明ransomNote 不能由 magazine 里面的字符构成。15. 三数之和给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。主要注意双指针和去重以及判断条件classSolution:defthreeSum(self,nums:list[int])-list[list[int]]:result[]nums.sort()foriinrange(len(nums)):ifnums[i]0:returnresultifi0andnums[i]nums[i-1]:continuelefti1rightlen(nums)-1whileleftright:sumsnums[i]nums[left]nums[right]ifsums0:leftleft1elifsums0:rightright-1else:result.append([nums[i],nums[left],nums[right]])whileleftrightandnums[left1]nums[left]:left1whileleftrightandnums[right-1]nums[right]:right-1left1right-1returnresult学习心得利用i和双指针leftright。首先sort()排序然后进入for循环判断数组里第一个元素是否0,是则返回[ ]。之后判断i0,nums[i-1] nums[i]去i的重复。定义left i 1。 right len(nums) - 1。之后进入循环while left right 判断sums是否0 0 0 ,大于0 则right - 1。小于0则left 1 等于零 则sums nums[ ] i left right 相加。 再进入left和right的去重。while left right and nums[left1] nums[left]: left。right同理。最后再来一个left和right–因为不一定会进入上一步的while循环。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你可以按 任意顺序 返回答案 。classSolution:deffourSum(self,nums:List[int],target:int)-List[List[int]]:nums.sort()result[]nlen(nums)foriinrange(n):ifnums[i]targetandtarget0:#剪枝breakifi0andnums[i]nums[i-1]:continueforjinrange(i1,n):ifnums[i]nums[j]targetandtarget0:#剪枝breakifji1andnums[j]nums[j-1]:continueleftj1rightn-1whileleftright:sumsnums[i]nums[j]nums[left]nums[right]ifsumstarget:right-1elifsumstarget:left1else:result.append([nums[i],nums[j],nums[left],nums[right]])whileleftrightandnums[left]nums[left1]:left1whileleftrightandnums[right]nums[right-1]:right-1left1right-1returnresult学习心得四数之和多了一个i和剪枝操作。其他没啥区别和三数之和。剪枝注意如果第一个数target and target0就break 第一个数加第二个数target and target0就break 其他都一样 i去重 j去重 left去重 right去重。