当前位置：首页 > article >正文

代码随想录刷题day16|（哈希表篇）349.两个数组的交集

article 2025/3/4 13:15:00

一、哈希表理论基础

二、集合set在哈希法中的应用

三、相关算法题目

四、相关知识点

1.set集合特点和常用方法

1.1 set集合概述

1.2 set集合特点

1.3 常用方法

2.set集合转换成数组

法1：另新建一个数组

法2：将结果集合转为数组 ▲

3.数组中元素放进set集合中

一、哈希表理论基础

详见代码随想录刷题day15|（哈希表篇）242.有效的字母异位词、383.赎金信-CSDN博客

二、集合set在哈希法中的应用

一般来说，给定一个元素，判断是否在集合中出现过，这种情况下考虑使用哈希表来解决问题；

本题力扣中限制了数据范围，所以也可以用数组来做，如果没有限制数据范围，那么不可以使用数组来做（数组的长度不可变），同时，如果数值很大、或者数值不太大，但很分散，比如0、5、100万，那么也不适合用数组来做；

本题需要注意的一点是：最终返回的数组中，每个元素都是唯一的，即去重的，因此可以使用set集合，利用set集合中数据元素不重复的特性；

思路：将数组nums1的元素放到一个哈希表中，java中可以采用HashSet集合：set，这样set集合中没有重复元素；遍历nums2数组，并在set集合中查找nums2中每一个元素是否出现过，如果出现过，则为相交部分元素，放在另一HashSet集合：result中，最终将result集合转成数组并返回；

为什么最终结果要放在集合result中？set保证了nums1中的元素不重复，但是nums2数组中元素也可能会重复，所以最终结果也可能会重复，所以需要放在result集合中；

补充：本题使用数组的思路

整体思路同使用set集合，具体实现上，将nums1数组中元素存储到哈希表中，此时哈希表使用数组array，用数组下标直接做哈希映射，将nums1中的每一个元素作为数组的索引值，即 array [ nums1[i] ]，并对该索引处的元素全部赋值为1，同时也能够达到去除重复数据的目的（如果有相同元素，在array中表现为对同一索引处的元素多次赋值为1）；

接着，遍历nums2，并在哈希数组中查找每一个元素：将nums2数组中的每一个元素作为array数组的索引值，查看对应索引值是否为1，如果为1，则说明是相交元素，否则，不是相交元素；

最后，将相交元素存入新建集合result中⚠️，这里使用集合是为了去除重复元素，最后再将集合转成数组，然后返回；

与set集合的区别：

使用set集合时，每add一个值，就要进行一次哈希运算，将该值转换成内部存储的一个值，同时需要开辟一个新的空间，相对数组来说，需要更多的时间，花费更高；

三、相关算法题目

349.两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

使用set集合：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //定义HashSet集合 
        HashSet<Integer> set =new HashSet<Integer>();
        HashSet<Integer> result =new HashSet<Integer>();
        //将nums1放到哈希表结构中 增强for循环▲ set无法使用普通for循环
        for(int c : nums1){
            set.add(c);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for(int c : nums2){
            if(set.contains(c)){
                result.add(c);
            }
        }
        //把set 转化成 数组
        //另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[result.size()];
        int j = 0;
        for(int c : result){
            arr[j++] = c;
        }
    return arr;
    }
}

使用数组：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //使用数组
        int[] array = new int[1002];//定义哈希数组
        HashSet<Integer> result = new HashSet<Integer>();//存放结果的集合 去除重复元素
        //将nums1中的元素 添加到哈希数组中
        for(int i = 0;i < nums1.length;i++){
            array[nums1[i]] = 1;
        }
        //遍历nums2数组 在哈希数组中查找对应元素
        for(int c : nums2){
            if(array[c] == 1){
                result.add(c);
            }
        }
        //新建数组 存储集合result中的结果
        int[] array2 = new int[result.size()];
        int i = 0;
        for(int c : result){
            array2[i] = c;
            i++;
        }
        return array2;
    }
}

四、相关知识点

1.set集合特点和常用方法

1.1 set集合概述

set集合的父类是collection（单列集合），set集合中常用的两个实现类为：HashSet 和 TreeSet，前者底层数据结构是哈希表，后者是红黑树；

定义set集合，set是接口，不可直接创建对象，只能通过实现类创建具体的对象；

Set<Integer> set = new HashSet<Integer>();

1.2 set集合特点

set集合：不可存储重复元素、没有索引，不能使用普通for循环遍历；
HashSet集合：set集合特点➕可以将元素按照规则进行排序；
TreeSet集合：set集合特点➕存取无序；

1.3 常用方法

几个常用方法：

boolean add(E e) ：向集合中添加元素；

boolean contains(Object o)：查找集合中是否存在元素o；

int size()：返回集合中元素个数；

Object[] toArray()：返回一个包含set集合中的所有元素的数组；

2.set集合转换成数组

法1：另新建一个数组

另外申请一个数组存放HashSet中的元素，最后返回数组；

int[] arr = new int[result.size()];
int j = 0;
for(int c : result){
    arr[j++] = c;
}

法2：将结果集合转为数组 ▲

result.stream().mapToInt(x -> x).toArray()；

resSet.stream()：
- 将 HashSet<Integer> 转换为一个流（Stream）。流是一种高级迭代器，可以对集合中的元素进行操作。
.mapToInt(x -> x)：
- 将流中的每个元素（Integer 类型）映射为 int 类型。x -> x 是一个Lambda表达式，表示将输入的 Integer 对象直接转换为其基本类型 int。
.toArray()：
- 将流中的 int 类型元素收集到一个数组中，返回一个 int[]。

最终，这行代码返回一个 int[] 类型的数组，其中包含集合 result中的所有元素。

PS：为什么 return result.toArray() 报错？▲

incompatible types: Object[] cannot be converted to int[]

这行代码尝试将一个集合（如 HashSet<Integer>）直接转换为数组。然而，toArray() 方法返回的是一个 Object[] 类型的数组，而不是 int[]。在Java中，Object[] 和 int[] 是不兼容的类型，因此不能直接将 Object[] 赋值给 int[]。