卷进大厂系列之LeetCode刷题笔记：两个数组的交集（简单）

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4]解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

涉及知识点

本题解题思路有很多，本文考虑两个解题思路：暴力解法和利用哈希表（对前面的优化）；

对于数组我们要知道以下内容：

• 数组是存储在连续内存空间的相同类型数据的集合
• 数组下标都是从0开始
• 数组在内存空间的地址都是连续的

对于哈希表我们要知道以下内容：

• 数组是一个简单的哈希表，其中哈希表中的关键码就是数组的索引下标
• 哈希表可以根据关键码直接访问数据（可以在 O(1) 的时间内判断一个元素是否在集合中）

那么根据题目，我们可以提炼的关键点：

• 两个数组求交集
• 输出元素唯一

这是一道简单题目，解决这道题目，其实主要是利用数组，暴力解法是最容易想到的，但这个很耗时，所以可以通过把数组当成哈希表来用，这样的话，可以在O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。

题目解答

Java题解一

思路分析
求两个数组的交集，直观的方法是遍历数组 1，对于其中的每个元素，遍历数组2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。

• 定义一个接收结果的list
• 使用双循环，遍历两个数组，找相同元素
• 相同元素添加到list中，结果返回

代码实现

class Solution {    public int[] intersection(int[] nums1, int[] nums2) { //暴力解法 List<Integer> res = new ArrayList<>(); //定义一个接收结果的list，用来存储重复元素 //双循环 for(int i = 0; i < nums1.length; i++){     for(int j = 0; j < nums2.length; j++){    if(nums1[i] == nums2[j] && !res.contains(nums1[i])){ //找两个数组相等的元素，且去重      res.add(nums1[i]); //满足条件的元素，添加到list中  }     } } int[] result = new int[res.size()]; //定义输出数组 for(int k = 0; k < res.size(); k++){     result[k] = res.get(k); //将list中的元素放入数组中 } return result; //返回结果数组    }}

Java题解二

思路分析

在上一个题解的基础上，使用哈希集合存储元素，则可以在 O(1)的时间内判断一个元素是否在集合中，从而降低时间复杂度。（思路是一样的）

• 创建两个哈希表，一个用来存数组1，一个用来存结果
• 先把数组1通过遍历的方式放入哈希表
• 遍历数组2，用来判断哈希表中是否存在相同元素
• 如果相同，就加入到结果哈希表中
• 最后再把结果哈希表放入新建数组中

class Solution {    public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set = new HashSet<>(); //创建一个哈希表，用来存数组1元素 Set<Integer> resSet = new HashSet<>(); //创建一个哈希表，用来存相同元素 //遍历数组1 for(int i : nums1){     set.add(i); //数组1的元素放入哈希表中 } //遍历数组2，用来判断哈希表中是否存在相同元素 for(int i: nums2){     if(set.contains(i)){ //判断哈希表中是否存在该元素  resSet.add(i); //将重复元素添加到哈希表中     } } int[] result = new int[resSet.size()]; //创建存放结果的数组 int index = 0; //数组中索引 for(int i : resSet){ //遍历具有相同元素的哈希表     result[index] = i; //将哈希表中的元素放入数组     index++;//数组后移一位 } return result; //返回结果数组    }}