两个数组的交集

LeetCode每日一题，349. Intersection of Two Arrays

先看题目描述

大意就是给定两个数组，让我们求其交集

算法和思路

哈希表+集合

大致想法就是先创建一个哈希表 map 和一个集合 nums，然后遍历 nums1 数组，将其中的每个数字作为 key 加入到 map 中，key 对应的 value 随便取就行，然后遍历 nums2 数组，对于其中的每个数字，判断 map 中是否包含此 key 值，若存在此 key 值，则将该数添加至集合 nums 中，最后将结果中数字依次添加至结果数组中即可

排序+双指针

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre 表示上一次加入答案数组的元素

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre ，将该数字添加到答案并更新 pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束

算法源码

哈希表+集合

import java.util.*;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        Set<Integer> nums = new HashSet<>();
        for (int num : nums1) {
            map.put(num, 1);
        }
        for (int num : nums2) {
            if (map.containsKey(num)) {
                nums.add(num);
            }
        }
        int[] res = new int[nums.size()];
        int i = 0;
        for (int num : nums) {
            res[i] = num;
            i++;
        }
        return res;
    }
}

排序+双指针

import java.util.*;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;
        int m = nums1.length;
        int n = nums2.length;
        int index = 0;
        int pre = Integer.MAX_VALUE;
        int[] intersection = new int[m + n];
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        while (i < m && j < n) {
            int num1 = nums1[i];
            int num2 = nums2[j];
            if (num1 < num2) {
                i++;
            } else  if (num1 > num2) {
                j++;
            } else {
                if (num1 != pre) {
                    intersection[index] = num1;
                    pre = num1;
                    index++;
                }
                i++;
                j++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

这里面的 Arrays.copyOfRange() 方法是第一次见到，可以快速复制数组的一部分，感觉还是很方便的

在看题解的评论时还看到了一种解法，虽然运行效率不高，但是使用的几个方法以前没见过，还是可以学习一下的

import java.util.*;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>(),set2 = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for(int i:nums1){
            list.add(i);
        }
        for(int i:nums2){
            set2.add(i);
        }
        list.retainAll(set2);
        set1.addAll(list);
        return set1.stream().mapToInt(i->i).toArray();
    }
}

这里的 retainAll() 方法以前没有见过，作用是可以求两个集合的交集，还有 set1.stream().mapToInt(i->i).toArray() 这种集合转数组的方法也没见过，我是遍历集合来转的数组，但测试了一下发现遍历集合转数组的方式是效率更高的

然后又看见了一个更骚的写法，这代码是真没看懂，但是运行效率太低

import java.util.*;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
        return Arrays.stream(nums2).distinct().filter(set::contains).toArray();
    }
}