349. 两个数组的交集

题目

349. 两个数组的交集

示例 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

要求

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

思路

这道题目脑海中的第一个印象就是暴力破解，使用双层 for 循环或者是分开遍历，用 Set 保存，用 contains 方法，代码如下：

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    for (int i : nums1) {
        set1.add(i);
    }
    Set<Integer> set2 = new HashSet<>();
    for (int i : nums2) {
        set2.add(i);
    }
    Set<Integer> set = new HashSet<>();
    for (Integer i : set1) {
        if (set2.contains(i)) {
            set.add(i);
        }
    }
    int[] result = new int[set.size()];
    int index = 0;
    for (Integer num : set) {
        result[index ++] = num;
    }
    return result;
}

题目要求无序，那还可以排序 + 双指针的思路，两个数组都排下序，然后两个指针 + while 循环，代码如下：

/**
 * 排序 + 双指针
 * @param nums1
 * @param nums2
 * @return
 */
public int[] intersection(int[] nums1, int[] nums2) {
    // 排序 + 双指针看看
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    Set<Integer> set = new HashSet<>();
    int nums1Point = 0;
    int nums2Point = 0;
    while (nums1Point < nums1.length && nums2Point < nums2.length) {
        if (nums1[nums1Point] == nums2[nums2Point]) {
            set.add(nums1[nums1Point]);
            nums1Point ++;
            nums2Point ++;
        } else if (nums1[nums1Point] > nums2[nums2Point]){
            nums2Point ++;
        } else {
            nums1Point ++;
        }
    }
    int[] result = new int[set.size()];
    int index = 0;
    for (Integer num : set) {
        result[index ++] = num;
    }
    return result;
}

第三个方法和之前的字母异位次类似，因为题目说了数组中的元素最大为 1000，包括 0 那就是 1001 个不同的数字，那我直接声明 1001 大小的数组，然后分开遍历，第一遍，给存在的元素索引 + 1，遍历第二个，判断索引位是否为 1，如果是则保存，并重置为 0，为了防止重复计算，代码如下：

/**
 * 根据提示来做，数组最长为 1000，那我声明一个 1001 大小的数组
 * @param nums1
 * @param nums2
 * @return
 */
public int[] intersection(int[] nums1, int[] nums2) {
    // 排序 + 双指针看看
    int[] arr = new int[1001];
    for (int i : nums1) {
        arr[i] = 1;
    }
    int index = 0;
    int[] result = new int[Math.max(nums1.length, nums2.length)];
    for (int i : nums2) {
        if (arr[i] == 1) {
            result[index ++] = i;
            // 重置的思路好呀
            arr[i] = 0;
        }
    }
    return Arrays.copyOfRange(result, 0, index);
}