题目地址(349. 两个数组的交集)

https://leetcode-cn.com/problems/intersection-of-two-arrays/

题目描述

  1. 给定两个数组，编写一个函数来计算它们的交集。
  5. 示例 1：
  7. 输入：nums1 = [1,2,2,1], nums2 = [2,2]
  8. 输出：[2]
  11. 示例 2：
  13. 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  14. 输出：[9,4]
  18. 说明：
  20. 输出结果中的每个元素一定是唯一的。
  21. 我们可以不考虑输出结果的顺序。

前置知识


公司

  • 暂无

思路

注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序
image.png
遇到哈希问题我直接都用set不就得了，用什么数组啊。
直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。
不要小瞧 这个耗时，在数据量大的情况，差距是很明显的

关键点


代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         public int[] intersection(int[] nums1, int[] nums2) {
  3.             //判断两个数组是否含有空值 如果有返回空数组
  4.             if (nums1 == null|| nums2 ==null || nums1.length == 0 || nums2.length == 0) {
  5.                 return new int[0];
  6.             }
  7.             //用于装nums1的不重复数字的数组
  8.             HashSet<Integer> set1 = new HashSet<>();
  9.             //根据set1 决定最终返回的数字
  10.             HashSet<Integer> set2 = new HashSet<>();
  11.             //由于set不会有重复的数字 所以add完之后只会有不重复的数字
  12.             for (int i : nums1) {
  13.                 set1.add(i);
  14.             }
  15.             for (int i : nums2) {
  16.                 //如果set1有该数字 则set2才添加 这样得到的就是两个数组的交集
  17.                 if (set1.contains(i)) {
  18.                     set2.add(i);
  19.                 }
  20.             }
  21.             //创建用于返回的数组 大小是set2的大小
  22.             int[] ints = new int[set2.size()];
  23.             int index = 0;
  24.             for (int i : set2) {
  25.                 ints[index++] = i;
  26.             }
  27.             return ints;
  28.         }
  29.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：349. 两个数组的交集 - 图2#card=math&code=O%28m%2Bn%29&id=odJ4i)
  • 空间复杂度：349. 两个数组的交集 - 图3#card=math&code=O%28n%29&id=KpMYm)