力扣题解——HashMap和HashSet的入门使用

力扣题解——HashMap和HashSet的入门使用

HashMap和HashSet的入门使用

• 349. 两个数组的交集
• • 问题分析
  • 过程分析
  • 整体代码
• 350. 两个数组的交集 II
• • 问题分析
  • 过程分析
  • 整体代码
• 总结

349. 两个数组的交集

看到题目以后有的小伙伴可能会想试图用数组对应创建哈希表来解决，但是我们会发现题目给出的数字并没有规定范围，所以数字的跨度可能会非常大，而且会很耗空间。

这里，我们可以直接使用Java内置的HashSet来解决此题

问题分析

题目要求我们输出的结果中，重复元素只记一次。而且，我们相当于是要查找nums1中的数字是否在nums2中出现过，根据这一思路，我们自然而然就会想到集合的性质。所以我们这里采用HashSet来实现查找的过程。

过程分析

首先我们要先将nums1中的数存入HashSet中

存入后大概是这个效果：

代码部分：

 Set nums=new HashSet<>();
     
     for(int i:nums1){
         nums.add(i);
     }

接下来我们要做的事情就很简单了，将nums2中的每个数字和HashSet中的数字比较就可以了

注：为了避免结果元素的重复，我们从nums2中遍历比较元素的时候，要将元素先放入另一个HashSet中，避免元素的重复。

代码部分：

Set res=new HashSet<>();
for(int i:nums2){
         if(nums.contains(i))
        res.add(i);
     }

最后，我们将res中的元素取出，放入需要返回的数组中即可

代码部分：

     int index=0;
     int[] resArr=new int[res.size()];
     for(int i: res){
         resArr[index]=i;
         index++;
     }

     return resArr;

整体代码

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
    //排除掉nums为空的情况
     if(nums1==null||nums1.length==0||nums2==null||nums2.length==0)
           return new int[0];
       //nums用来创建nums1的HashSet，res用来保存遍历对比nums2中元素的结果
       Set nums=new HashSet<>();
       Set res=new HashSet<>();
       //将nums1中的元素存入numns中
       for(int i:nums1){
         nums.add(i);
       }
       //遍历nums2中的元素，与nums中的元素相比较；若存在，存入res中
       for(int i:nums2){
         if(nums.contains(i))
        res.add(i);
       }
     //将res转换为数组
     int index=0;
     int[] resArr=new int[res.size()];
     for(int i: res){
         resArr[index]=i;
         index++;
     }

     return resArr;
     

    }
}

350. 两个数组的交集 II

这题是不是和刚刚那题很相似?仔细阅读题目我们可以发现，这题我们就不能用集合去实现了。我们要记下同一组中重复出现元素的个数，我们就可以考虑用HashMap来实现。

问题分析

和上一题类似，区别是我们需要将重复元素也算进去。显然，用集合是行不通了，所以我们这里用到图来解决这一问题

过程分析

我们这里将key值定为元素值，value定为该元素出现的次数就行了

代码部分：

     Map nums=new HashMap<>();

        for(int i:nums1){
            int cur=nums.getOrDefault(i,0)+1;
            nums.put(i,cur);
        }

然后我们再遍历nums2中的元素，与nums中的元素比较

注：当寻找到有重复元素时，要改变对应的value值

代码实现

        int[] res=new int[nums1.length];
        int index=0;
        for(int i:nums2){
            int count=nums.getOrDefault(i,0);
            if(count>0){
              res[index]=i;
              index++;
              count--;
              if(count>0)
                nums.put(i,count);
            else
              nums.remove(i);
            }
        }

整体代码

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1==null||nums1.length==0||nums2==null||nums2.length==0)
           return new int[0];
        Map nums=new HashMap<>();

        for(int i:nums1){
            int cur=nums.getOrDefault(i,0)+1;
            nums.put(i,cur);
        }
        int[] res=new int[nums1.length];
        int index=0;
        for(int i:nums2){
            int count=nums.getOrDefault(i,0);
            if(count>0){
            res[index]=i;
            index++;
            count--;
            if(count>0)
            nums.put(i,count);
            else
             nums.remove(i);
            }
        }

        return Arrays.copyOfRange(res, 0, index);

    }
}

总结

两道题都是对哈希表的基本运用，主要需要我们读清题意，判断是选用图还是列表，然后熟悉哈希表的基本用法可以比较容易写出这两道题目了。