题目描述

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。

我们可以 不考虑输出结果的顺序 。

输入输出

1
2
3
4
5
6
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

基本思路

  1. 方法一：排序+双指针法 时复$O(mlogm+nlogn)$ 空复$O(logm+logn)$

    数组排序，然后用两个指针分别遍历数组，如果两个指针指向的元素相等 就是其中一个交集，否则比较两个指针指向的元素的大小，较小的向前移动 超出时间限制

  2. 方法二：集合 时复$O(m+n)$ 空复$O(m+n)$

    先将数组转成Set，然后判断Set1中的元素是否存在于Set2中，存在的话就是其中一个交集。

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//方法一 超出时间限制
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int[] interarray = new int[length1 + length2];
        Arrays.sort(nums1);Arrays.sort(nums2);
        int index = 0, index1 = 0, index2 = 0;
        while(index1 < length1 && index2 < length2) {
            int num1 = nums1[index1];
            int num2 = nums2[index2];
            if(num1 == num2) {
                if(index == 0 || num1 != interarray[index - 1]){
                    interarray[index++] = num1;
                }
            }
            else if(num1 < num2) {
                index1++;
            }
            else{
                index2++;
            }
        }
        return Arrays.copyOfRange(interarray, 0, index);
    }
}

//方法二
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int index = 0;
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for(int num1:nums1) {
            set1.add(num1);
        }
        for(int num2:nums2){
            set2.add(num2);
        }

        Set<Integer> interset = new HashSet<Integer>();
        for(int num:set1){
            if(set2.contains(num)){
                interset.add(num);
            }
        }
        int[] interarray = new int[interset.size()];
        for(int i:interset){
            interarray[index++] = i;
        }
        return interarray; 
    }
}