devbox
小舞很执着
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：小舞很执着 | 2024-08-07 15:48:43

赞

踩

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

写在前边的话

        今天是哈希表训练的第二天，哈希表相关的基础知识在昨天已经总结过了，看到今天的四道题目感觉还是比较有挑战的，那就加油吧！

454.四数相加II 

题目链接

        力扣454. 四数相加||

题目难度

        中等

看到题目的第一想法

        看到题目就想到了要使用哈希表，由于统计的是数量，因此就要选择python中的字典或者Java中的HashMap了，这样可以保存键值对。

看完代码随想录以后的总结

解题思路

        1. 使用哈希表。

        2. 前两个数组的和以及出现的次数作为键值对先存储。

        3. 检查后两个数组和的相反数有没有在哈希表中出现过，出现则获取次数。

文章讲解

        代码随想录454. 四数相加||文章讲解

视频讲解

        代码随想录454. 四数相加||视频讲解

代码编写

        python

  1. class Solution:
  2.     def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
  3.         dic = {}
  4.         res = 0
  5.  
  6.         # 遍历前两个数组并记录和以及出现的次数
  7.         for i in nums1:
  8.             for j in nums2:
  9.                 snum = i+j 
  10.                 dic[snum] = dic.get(snum, 0) + 1
  11.  
  12.         # 遍历后两个数组并检查和的相反数有没有出现在dic中, 出现了累加数量
  13.         for  i in nums3:
  14.             for j in nums4:
  15.                 snum = 0 - (i+j)
  16.                 if snum in dic:
  17.                     res += dic[snum]
  18.  
  19.         return res
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2) 最坏情况

        Java

  1. class Solution {
  2.     public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
  3.         HashMap<Integer, Integer> hash = new HashMap<>();
  4.         int res = 0;
  5.         for(int i: nums1){
  6.             for(int j: nums2){
  7.                 int sum = i+j;
  8.                 int count = hash.getOrDefault(sum, 0);
  9.                 hash.put(sum, count+1);
  10.             }
  11.         }
  12.  
  13.         for(int i: nums3){
  14.             for(int j: nums4){
  15.                 int sum = 0 - (i+j);
  16.                 if(hash.containsKey(sum)){
  17.                     res += hash.get(sum);
  18.                 }
  19.             }
  20.         }
  21.  
  22.         return res;
  23.     }
  24. }
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2) 最坏情况

383. 赎金信

题目链接

        力扣383. 赎金信

题目难度

        简单

看到题目的第一想法

        看到题目的第一想法是要使用哈希表，由于要保存字符及数量因此要用字典或者HashMap，不同点是两个数组的大小不一定相等。

  python

  1. class Solution:
  2.     def canConstruct(self, ransomNote: str, magazine: str) -> bool:
  3.         if len(magazine) < len(ransomNote):
  4.             return False
  5.  
  6.         dic = {}
  7.         for m in magazine:
  8.             dic[m] = dic.get(m, 0) + 1
  9.  
  10.         for r in ransomNote:
  11.             if r not in dic:
  12.                 return False
  13.             dic[r] -= 1
  14.             if dic[r] < 0:
  15.                 return False
  16.         return True
  • 时间复杂度：O(m+n)，m, n分别是数组magazine，ransomNote的长度
  • 空间复杂度： O(m)

        Java

  1. class Solution {
  2.     public boolean canConstruct(String ransomNote, String magazine) {
  3.         if(magazine.length() < ransomNote.length()){
  4.             return false;
  5.         }
  6.         HashMap<Character, Integer> hash = new HashMap<>();
  7.         for(int i=0; i < magazine.length(); i++){
  8.             int count = hash.getOrDefault(magazine.charAt(i), 0) + 1;
  9.             hash.put(magazine.charAt(i), count);
  10.         }
  11.  
  12.         for(int i=0; i < ransomNote.length(); i++){
  13.             if(!hash.containsKey(ransomNote.charAt(i))){
  14.                 return false;
  15.             }
  16.  
  17.             int count = hash.get(ransomNote.charAt(i)) - 1;
  18.             if(count < 0){
  19.                 return false;
  20.             }else{
  21.                 hash.put(ransomNote.charAt(i), count);
  22.             }
  23.         }
  24.         return true;
  25.     }
  26. }
  • 时间复杂度：O(m+n)
  • 空间复杂度： O(m)

看完代码随想录以后的总结

解题思路

        1. 解题思路和有效的字母异位词解法类似，使用数组（由于字符是有范围的，所以可以定义一个常量大小的数组，很大程度降低了空间复杂度）。

文章讲解

        代码随想录383. 赎金信文章讲解

代码编写

        python

  1. class Solution:
  2.     def canConstruct(self, ransomNote: str, magazine: str) -> bool:
  3.         if len(magazine) < len(ransomNote):
  4.             return False
  5.  
  6.         count = [0] * 26
  7.         for i in magazine:
  8.             index = ord(i) - ord('a')
  9.             count[index] += 1
  10.  
  11.         for i in ransomNote:
  12.             index = ord(i) - ord('a')
  13.             if count[index] < 1:
  14.                 return False
  15.  
  16.             count[index] -= 1
  17.         return True
  • 时间复杂度：O(m+n)
  • 空间复杂度：O(1)

        Java

  1. class Solution {
  2.     public boolean canConstruct(String ransomNote, String magazine) {
  3.         if(magazine.length() < ransomNote.length()){
  4.             return false;
  5.         }
  6.         int[] count = new int[26];
  7.         for(int i=0; i < magazine.length(); i++){
  8.             int index = magazine.charAt(i) - 'a';
  9.             count[index] += 1;
  10.         }
  11.  
  12.         for(int i = 0; i < ransomNote.length(); i++){
  13.             int index = ransomNote.charAt(i) - 'a';
  14.             if(count[index] < 1){
  15.                 return false;
  16.             }else{
  17.                 count[index] -= 1;
  18.             }
  19.         }
  20.         return true;
  21.     }
  22. }
  • 时间复杂度：O(m+n)
  • 空间复杂度：O(1) 

15. 三数之和

题目链接

        力扣15. 三数之和

题目难度

        简单        

看到题目的第一想法

        没什么好的解题思路，想用哈希表，但是也没有梳理好去重的思路。

看完代码随想录以后的总结

解题思路

        1. 先对数组排序。

        2. 使用双指针法寻找当前和nums[i] 和为0的组合。

         3. 注意去重：1）对nums[i]去重；2）当找到满足和为0的三个数以后对下一个nums[left]和nums[right去重]。      

文章讲解

        代码随想录15. 三数之和文章讲解        

视频讲解

        代码随想录15. 三数之和视频讲解

代码编写

        python

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         res = []
  4.         nums.sort() # 排序
  5.  
  6.         for i in range(len(nums)):
  7.             # 剪枝 如果nums[i] > 0 则就结束循环
  8.             if nums[i] > 0:
  9.                 break
  10.  
  11.             # 对num[i]去重, 当前值与上次循环的值一样了，则当前循环就不再走下去了，进入下一循环
  12.             if(i>0 and nums[i] == nums[i-1]):
  13.                 continue
  14.  
  15.             # 设置left right的起始位置
  16.             left = i+1
  17.             right = len(nums) - 1
  18.  
  19.             # 查找与当前nums[i]和为0的nums[left]和nums[right]
  20.             while(left < right):
  21.                 snum = nums[i] + nums[left] + nums[right]
  22.                 if snum > 0:
  23.                     right -= 1
  24.                 elif snum < 0:
  25.                     left += 1
  26.                 else:
  27.                     res.append([nums[i], nums[left], nums[right]])
  28.                     left += 1
  29.                     right -= 1
  30.                     # 注意这里需要对下一个nums[left]和nums[right]判断是否和当前值相同
  31.                     while(left < right and nums[left] == nums[left-1]):
  32.                         left += 1
  33.                     while(left < right and nums[right] == nums[right+1]):
  34.                         right -= 1
  35.         return res
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2) 最坏情况

        Java

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         List<List<Integer>> resList = new ArrayList<>();
  4.         Arrays.sort(nums);  
  5.         
  6.         for(int i=0; i < nums.length; i++){
  7.             if(nums[i] > 0){
  8.                 break;
  9.             }
  10.  
  11.             if(i > 0 && nums[i] == nums[i-1]){
  12.                 continue;
  13.             }
  14.  
  15.             int left = i+1;
  16.             int right = nums.length - 1;
  17.             while(left < right){
  18.                 int sum = nums[i] + nums[left] + nums[right];
  19.                 if(sum > 0){
  20.                     right--;
  21.                 }else if(sum < 0){
  22.                     left++;
  23.                 }else{
  24.                     resList.add(Arrays.asList(nums[i], nums[left],nums[right]));  //Arrays.asList将数组转换成list
  25.                     left++;
  26.                     right--;
  27.  
  28.                     while(left < right && nums[left] == nums[left-1]){
  29.                         left++;
  30.                     }
  31.                     while(left < right && nums[right] == nums[right+1]){
  32.                         right--;
  33.                     }
  34.                 }
  35.             }
  36.  
  37.         }
  38.         return resList;
  39.     }
  40. }
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2) 最坏情况

18. 四数之和

题目链接

        力扣18. 四数之和

题目难度

        中等

看到题目的第一想法

        看道这个题目的时候，结合上一道题目，想到的使用双指针法，但是没能梳理出来比较好的思路。

看完代码随想录以后的总结

解题思路

        1. 使用指针法

        2. 和三个数的和解法类型，只是增加了一层循环，同样需要注意去重。

文章讲解

        代码随想录18. 四数之和

视频讲解

        代码随想录18. 四数之和视频讲解

代码编写

        python

  1. class Solution:
  2.     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
  3.         res = []
  4.         nums.sort()  # 首先还是要先排序
  5.         n = len(nums)
  6.  
  7.         # 两层循环遍历拿到四元组的前两个数据
  8.         for i in range(n):
  9.             if target > 0 and nums[i] > target:   # 适当剪枝
  10.                 break
  11.  
  12.             if i > 0 and nums[i] == nums[i-1]:  # 去重
  13.                 continue
  14.  
  15.             for j in range(i+1, n):
  16.                 if target > 0 and nums[i] + nums[j] > target:  # 剪枝
  17.                     break
  18.  
  19.                 if j > i+1 and nums[j] == nums[j-1]:   #  去重
  20.                     continue
  21.  
  22.                 # 接下来开始找四元组剩下的两个数了，和三数之和逻辑一样设置left right指针
  23.                 left = j+1
  24.                 right = n-1
  25.                 while left < right:
  26.                     snum = nums[i] + nums[j] + nums[left] + nums[right]
  27.                     if snum > target:
  28.                         right -= 1
  29.                     elif snum < target:
  30.                         left += 1
  31.                     else:
  32.                         res.append([nums[i], nums[j], nums[left], nums[right]])
  33.                         left += 1   # 找到目标以后，一起移动left和right到下一个位置
  34.                         right -= 1
  35.  
  36.                         # 接下来就要对 left right去重了
  37.                         while left < right and nums[left] == nums[left - 1]: 
  38.                             left += 1
  39.                         while left < right and nums[right] == nums[right + 1]:
  40.                             right -= 1
  41.         return res
  • 时间复杂度：O(n^3)
  • 空间复杂度： O(n^3) 最坏

        java

  1. class Solution {
  2.     public List<List<Integer>> fourSum(int[] nums, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         Arrays.sort(nums);
  5.         int n = nums.length;
  6.  
  7.         for(int i=0; i<n; i++){
  8.             if(target > 0 && nums[i] > target){
  9.                 break;
  10.             }
  11.  
  12.             if(i > 0 && nums[i] == nums[i-1]){
  13.                 continue;
  14.             }
  15.  
  16.             for(int j=i+1; j<n; j++){
  17.                 if(target > 0 && nums[i] + nums[j] > target){
  18.                     break;
  19.                 }
  20.  
  21.                 if(j > i+1 && nums[j] == nums[j-1]){
  22.                     continue;
  23.                 }
  24.  
  25.                 int left = j+1;
  26.                 int right = n-1;
  27.                 while(left < right){
  28.                     long sum = (long)nums[i] + nums[j] + nums[left] + nums[right]; // 坑点要用long数据类型，不然会导致超过整型最大值溢出 eg: 测试用例 nums = [1000000000,1000000000,1000000000,1000000000] target = -294967296
  29.                     if(sum > target){
  30.                         right--;
  31.                     }else if(sum < target){
  32.                         left++;
  33.                     }else{
  34.                         res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
  35.                         left++;
  36.                         right--;
  37.                         while(left < right && nums[left] == nums[left-1]){
  38.                             left++;
  39.                         }
  40.                         while(left < right && nums[right] == nums[right+1]){
  41.                             right--;
  42.                         }
  43.                     }
  44.                 }
  45.             }
  46.         }
  47.     return res;
  48.     }
  49. }
  • 时间复杂度：O(n^3)
  • 空间复杂度： O(n^3) 最坏 

 今日总结

        感觉又是比较烧脑的一天，但是也有很多收获，在数据量比小且有一定范围的时候，我们可以使用数组，这样空间复杂度就会大大减少；在做三数之和四书之和的时候我们通常使用指针的方法；注意java语言的整型溢出，这是今天踩到的一个坑点。总的来说虽说哈希表的使用比昨天顺手一点了，但是新增的三数之和四数之和的思维还局限在哈希表中，切记思维定式，周末的时候再回顾一下吧。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号