刷题力扣349-两个数组的交集

水深无声 2024-04-08 09:00 25阅读 0赞

这道题代码随想录用的是哈希数据结构，什么时候用哈希表，哈希表都是用来快速判断一个元素是否出现在集合里，相对于枚举的话，哈希表的时间复杂度只有O(1)。

常见的三种哈希结构

> 数组
> 
> set（集合）
> 
> map（映射）

当出现快速判断一个元素是否出现在集合里的时候，就要考虑哈希法，牺牲空间换取时间。

题目描述：

题意：给定两个数组，编写一个函数来计算它们的交集。

![4957ae8e496842c3a447fdb2acd2bba4.png][]

说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

在不考虑数量的情况下，假设数据有无穷大，我们可以用set的哈希结构去解这道题。在java中使用set，可以得到一个不包含重复元素的集合，而且set无序，且允许出现null元素。

set方法：

boolean add(E e) //如果 set 中尚未存在指定的元素，则添加此元素（可选操作）。
    boolean addAll(Collection<? extends E> c) //如果 set 中没有指定 collection 中的所有元素，则将其添加到此 set 中（可选操作）。
    void 　　clear() //移除此 set 中的所有元素（可选操作）。
    boolean contains(Object o) //如果 set 包含指定的元素，则返回 true。
    boolean containsAll(Collection<?> c) //如果此 set 包含指定 collection 的所有元素，则返回 true。
    boolean equals(Object o) //比较指定对象与此 set 的相等性。
    int 　　 hashCode() //返回 set 的哈希码值。
    boolean isEmpty() //如果 set 不包含元素，则返回 true。
    Iterator<E> iterator() //返回在此 set 中的元素上进行迭代的迭代器。
    boolean remove(Object o) //如果 set 中存在指定的元素，则将其移除（可选操作）。
    boolean removeAll(Collection<?> c) //移除 set 中那些包含在指定 collection 中的元素（可选操作）。
    boolean retainAll(Collection<?> c) //仅保留 set 中那些包含在指定 collection 中的元素（可选操作）。
    int 　　 size() //返回 set 中的元素数（其容量）。
    Object[] toArray() //返回一个包含 set 中所有元素的数组。
    <T> T[] toArray(T[] a) //返回一个包含此 set 中所有元素的数组；返回数组的运行时类型是指定数组的类型。

解题思路：

将nums1的集合元素放到一个set集合里，然后去遍历nums2集合元素，如果nums2集合元素在set集合里出现，我们就可以把该元素的下标放到结果的set集合里。set集合存放的其实就是一个下标与元素的映射关系。

代码：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
    if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
    return new int[0];
    }
    Set<Integer> set1 = new HashSet<>(); //用于存放nums1的元素
    Set<Integer> resSet = new HashSet<>(); //用于存放交集的元素
    for(int i : nums1){
    set1.add(i);
    }
    for(int i : nums2){
    if(set1.contains(i)){ //如果nums2的元素在set1中出现，把该元素下标放到resSet集合中
    resSet.add(i);
    }
    }
    //将结果集合转为数组-法一
    return resSet.stream().mapToInt(x->x).toArray();
    
    //将结果集合转为数组-法二
    int[] resArr = new int[resSet.size()];
    int index = 0;
    for(int i : resSet1){
    resArr[index++] = i;
    }
    
    return resArr;
    }

力扣这道题后来把数据范围限制在1000以内，那么可以用数组来写，java如果用数组做哈希结构的话，代码方法如下：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
    if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
    return new int[0];
    }
    int[] hash = new int[1005];
    Set<Integer> resSet = new HashSet<>(); //存放结果是为了去重
    for(int i : nums1){ //对于nums1中出现过的元素，在hash数组中做记录
    hash[i] = 1;
    }
    for(int i : nums2){
    if(hash[i] == 1){
    resSet.add(i);
    }
    }
    int[] result = new int[resSet.size()];
    int index = 0;
    for(int i : resSet){
    result[index++] = i;
    }
    return result;
    }
    }

[4957ae8e496842c3a447fdb2acd2bba4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/8498f51d5eab415bb3e776566c86a86d.png