349-两个数组的交集

题目地址(349. 两个数组的交集 - 力扣（LeetCode）)

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

题目描述

给定两个数组 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

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] hash1 = new int[1002];
        int[] hash2 = new int[1002];
        // 计数
        for(int i : nums1)
            hash1[i]++;
        for(int i : nums2)
            hash2[i]++;
        List<Integer> resList = new ArrayList<>();
        // 寻找交集元素
        for(int i = 0; i < 1002; i++)
            if(hash1[i] > 0 && hash2[i] > 0)
                resList.add(i);
        // 转换成数组
        int index = 0;
        int res[] = new int[resList.size()];
        for(int i : resList)
            res[index++] = i;
        return res;
    }
}

复杂度分析

令 n 为nums1数组长度,m为nums2数组长度。

• 时间复杂度：$O(m+n)$,使用两个集合分别存储两个数组中的元素需要 $O(m+n)$ 的时间

• 空间复杂度：$O(m+n)$，两个存储数组都是固定长度。