求两数组交集【LeetCode:349】

题目

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

• 示例 1:

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

• 示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

• 说明:

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

解析

想了两种思路：

1. 针对短的那个数组进行排序，然后遍历长的那个，查找短的数组中是否存在相同元素。排序可以用快排，查找用二分查找。

2. 第二种，针对其中一个数字建立hash索引，遍历第二个数组，在第一个中查找。（最后采用的思路，第一种写起来太麻烦）

实现

java实现，用时3ms

int[] intersection(int[] nums1, int[] nums2) {
    int length1 = nums1.length;
    int length2 = nums2.length;
    if (length1 == 0 || length2 == 0) {
        return new int[0];
    }
    Set<Integer> set1 = new HashSet<>(length1);
    for (int value : nums1) {
        set1.add(value);
    }
    Set<Integer> result = new HashSet<>(length1);
    for (int value : nums2) {
        if (set1.contains(value)) result.add(value);
    }
    int[] r = new int[result.size()];
    int count = 0;
    for (Integer value : result) {
        r[count++] = value;
    }
    return r;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays