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

day6 – 哈希表part02454.四数相加力扣题目链接454. 四数相加 II - 力扣LeetCode文章讲解第454题.四数相加II | 哈希表 | map | 统计查找 | 代码随想录视频讲解学透哈希表map使用有技巧LeetCode454.四数相加II_哔哩哔哩_bilibilipublicclassSolution{publicintFourSumCount(int[]nums1,int[]nums2,int[]nums3,int[]nums4){intnnums1.Length;Dictionaryint,intn12newDictionaryint,int();//a,b两数之和 -- 出现的次数Dictionaryint,intn34newDictionaryint,int();//分治思想intcount0;for(inti0;in;i){//记录n12for(intj0;jn;j){inttmpnums1[i]nums2[j];if(!n12.ContainsKey(tmp)){n12.Add(tmp,1);}else{n12[tmp];}}}for(inti0;in;i){//记录n34for(intj0;jn;j){inttmpnums3[i]nums4[j];if(!n34.ContainsKey(tmp)){n34.Add(tmp,1);}else{n34[tmp];}}}foreach(intiinn12.Keys){//遍历计数if(n34.ContainsKey(-i)){countn12[i]*n34[-i];}}returncount;}}383.赎金信力扣题目链接383. 赎金信 - 力扣LeetCode文章讲解383. 赎金信 | 哈希法 | 数组 | 代码随想录很简单的记录和查找是否有匹配字母只是运用了哈希表Dictionary降低了查找步骤的时间复杂度publicclassSolution{publicboolCanConstruct(stringransomNote,stringmagazine){Dictionarychar,inthnewDictionarychar,int();foreach(chariinmagazine){if(!h.ContainsKey(i)){h.Add(i,1);}else{h[i];}}foreach(chariinransomNote){if(!h.ContainsKey(i)){returnfalse;}else{h[i]--;if(h[i]0){h.Remove(i);}}}returntrue;}}15.三数之和力扣题目链接15. 三数之和 - 力扣LeetCode文章讲解第15题. 三数之和 | 双指针 | 哈希法 | 去重 | 代码随想录视频讲解梦破碎的地方| LeetCode15.三数之和_哔哩哔哩_bilibili如果用哈希法做此题去重操作会十分繁琐容易超时故有双指针做法publicclassSolution{publicIListIListintThreeSum(int[]nums){ListIListintansnewListIListint();//List继承IList接口Array.Sort(nums);for(inti0;inums.Length-2;i){if(nums[i]0){break;}//剪枝//去重第一个数字if(i0nums[i]nums[i-1])continue;// 注意不能是nums[i] nums[i 1]哦intrightnums.Length-1;intlefti1;while(leftright){intsumnums[i]nums[left]nums[right];if(sum0){right--;}elseif(sum0){left;}else{//sum 0ans.Add(newListint{nums[i],nums[left],nums[right]});//去重后两个数字left;right--;//不可能只变动一个还有正解while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;//leftright确保不会一直加或者一直减到越界}}}returnans;}}较为复杂详见讲解18.四数之和力扣题目链接18. 四数之和 - 力扣LeetCode文章讲解第18题. 四数之和 | 双指针法 | 剪枝去重 | 代码随想录视频讲解难在去重和剪枝| LeetCode18. 四数之和_哔哩哔哩_bilibili三数之和多加一层for循环publicclassSolution{publicIListIListintFourSum(int[]nums,inttarget){//先排序Array.Sort(nums);ListIListintansnewListIListint();for(inti0;inums.Length-3;i){//去重第一个数字if(i0nums[i]nums[i-1]){continue;}for(intji1;jnums.Length-2;j){//去重第二个数字if(ji1nums[j]nums[j-1]){continue;}intleftj1;intrightnums.Length-1;while(leftright){longsum(long)nums[i]nums[j]nums[left]nums[right];if(sumtarget){left;}elseif(sumtarget){right--;}else{//sum targetans.Add(newListint{nums[i],nums[j],nums[left],nums[right]});//去重后两个数字left;right--;while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;}}}}returnans;}}