数组相交

349. 两个数组的交集

基础方法

    public int[] intersection(int[] nums1, int[] nums2) {
        if( nums1 ==null || nums2 == null || nums1.length == 0 || nums2.length == 0)
            return new int[0];
        HashSet<Integer> set = new HashSet<>();
        HashSet<Integer> ans = new HashSet<>();
        for (int i : nums1){
            set.add(i);
        }
        for (int i : nums2){
            if (set.contains(i) && !set.add(i)){
                //问题出在，如果第二个集合有相同元素，也会添加失败
                //所以添加添加前还应判断，是否有必要添加，如果第一个集合根本没出现，那还添加个几把
                //可以直接去掉第二个条件，因为包含不就是交集元素
                ans.add(i);
            }
        }
        int[] res = new int[ans.size()];
        int idx = 0;
        for (int i : ans){
            res[idx++] = i;
        }
        return res;
    }

进阶方法1、精通java集合的调用

    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();
    }

进阶方法2、精通stream的调用

    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();
    }

350. 两个数组的交集 II

在上题的基础上额外要求

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[Math.min(length1, length2)];
        int index1 = 0, index2 = 0, index = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection[index] = nums1[index1];
                index1++;
                index2++;
                index++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}