https://leetcode.cn/problems/intersection-of-two-arrays/

题面

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

349. 两个数组的交集

思路① 暴力，时间O(n^2)

思路② 哈希，时间O(m+n)，空间O(n)

版本一：使用HashSet

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
public int[] intersection(int[] nums1, int[] nums2) {
	if (nums1 == null || nums1.length == 0 || nums2 == null || nums.length == 0) {
		return new int[0];
	}
	Set<Integer> set1 = new HashSet<>();
	Set<Integer> resSet = new HashSet<>();
	// 遍历数组1
	for (int i : nums1) {
		set1.add(i);
	}
	// 遍历数组2的过程中判断哈希表中是否存在该元素
	for (int i : nums2) {
		if (set1.contains(i)) {
            resSet.add(i);
        }
	}
    
    // 方法1：将结果集合转化为数组
    return resSet.stream().mapToInt(x -> x).toArray();
    
    // 方法2：另外申请一个数组存放setRes中的元素，最后返回数组
    int[] arr = new int[resSet.size()];
    int j = 0;
    for (int i : resSet) {
        arr[j++] = i;
    }
    return arr;
}

版本二：使用Hash数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] intersection(int[] nums1, int[] nums2) {
    int[] hash1 = new int[1002];
    int[] hash2 = new int[1002];
    for (int i : nums1)
        hash1[i]++;
    for (int i : nums2)
        hash2[i]++;
    List<Integer> resList = new ArrayList<>();
    for (int i = 0; i < 1002; i++)
        if (hash1[i] > 0 && hash2[i] > 0)
            resList.add(i);
    int index = 0;
    int res[] = new int[resList.size()];
    for (int i : resList)
        res[index++] = i;
    return res;
}