LeetCode 349. 两个数组的交集

Categories:

Tags:

题目描述
思路分析
1. 解法一：哈希集合（推荐）
2. 解法二：排序 + 双指针
相似题目

题目描述

✅ 349. 两个数组的交集

思路分析

解法一：哈希集合（推荐）

核心思路：

将 nums1 中的所有元素存入哈希集合 set1，自动去重。

遍历 nums2，若当前元素存在于 set1 中，则加入结果集，并从 set1 删除该元素，保证结果唯一。

最终返回结果集即为两数组的交集。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为 nums1、nums2 的长度，各遍历一次。

空间复杂度：O(m)，哈希集合最多存储 nums1 的所有元素。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        // 将 nums1 所有元素存入哈希集合
        for (int num : nums1) {
            set1.add(num);
        }

        Set<Integer> resSet = new HashSet<>();
        // 遍历 nums2，找出在 set1 中存在的元素
        for (int num : nums2) {
            if (set1.contains(num)) {
                resSet.add(num);
            }
        }

        // 将结果集转为数组
        int[] res = new int[resSet.size()];
        int idx = 0;
        for (int num : resSet) {
            res[idx++] = num;
        }
        return res;
    }
}

func intersection(nums1 []int, nums2 []int) []int {
	set1 := make(map[int]struct{})
	// 将 nums1 所有元素存入哈希集合
	for _, num := range nums1 {
		set1[num] = struct{}{}
	}

	resSet := make(map[int]struct{})
	// 遍历 nums2，找出在 set1 中存在的元素
	for _, num := range nums2 {
		if _, ok := set1[num]; ok {
			resSet[num] = struct{}{}
		}
	}

	// 将结果集转为切片
	res := make([]int, 0, len(resSet))
	for num := range resSet {
		res = append(res, num)
	}
	return res
}

解法二：排序 + 双指针

核心思路：

对 nums1 和 nums2 分别排序。

使用两个指针 i、j 分别指向两个数组的起始位置，同步推进：

若 nums1[i] == nums2[j]，且与上一个加入结果的元素不同，则加入结果；两指针同时右移。

若 nums1[i] < nums2[j]，则 i 右移。

否则 j 右移。

利用排序后相同元素相邻的性质，天然去重。

复杂度分析：

时间复杂度：O(m log m + n log n)，其中 m、n 分别为 nums1、nums2 的长度，排序主导。

空间复杂度：O(log m + log n)，排序所需的递归栈空间。

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0, j = 0;
        List<Integer> resList = new ArrayList<>();

        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                // 避免重复加入相同元素
                if (resList.isEmpty() || resList.get(resList.size() - 1) != nums1[i]) {
                    resList.add(nums1[i]);
                }
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }

        // 将结果集转为数组
        int[] res = new int[resList.size()];
        for (int k = 0; k < resList.size(); k++) {
            res[k] = resList.get(k);
        }
        return res;
    }
}

func intersection(nums1 []int, nums2 []int) []int {
	sort.Ints(nums1)
	sort.Ints(nums2)

	i, j := 0, 0
	res := []int{}

	for i < len(nums1) && j < len(nums2) {
		if nums1[i] == nums2[j] {
			// 避免重复加入相同元素
			if len(res) == 0 || res[len(res)-1] != nums1[i] {
				res = append(res, nums1[i])
			}
			i++
			j++
		} else if nums1[i] < nums2[j] {
			i++
		} else {
			j++
		}
	}

	return res
}

相似题目

题目	难度	考察点
350. 两个数组的交集 II	简单	哈希表 / 排序 + 双指针
1. 两数之和	简单	哈希表 / 查找
242. 有效的字母异位词	简单	哈希表 / 字符统计
202. 快乐数	简单	哈希表 / 快慢指针
454. 四数相加 II	中等	哈希表 / 分组统计
560. 和为 K 的子数组	中等	哈希表 / 前缀和
217. 存在重复元素	简单	哈希表 / 集合去重

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/72990362