当前位置：首页 > news >正文

【算法系列-哈希表】两个集合的交集问题

news 2025/8/30 13:27:17

【算法系列-哈希表】两个集合的交集问题

文章目录

【算法系列-哈希表】两个集合的交集问题
- 1. 两个集合的交集问题(LeetCode 349)
- - 1.1 思路分析🎯
  - 1.2 代码示例🌰
- 2.两个集合的交集问题II(LeetCode 350)
- - 2.1 思路分析🎯
  - 2.2 代码示例🌰

1. 两个集合的交集问题(LeetCode 349)

【题目链接】349. 两个数组的交集 - 力扣（LeetCode）

1.1 思路分析🎯

利用集合类set存储数组nums1出现的所有元素，并去掉重复项之后遍历数组nums2，每次判断当前元素是否存在于集合类中，存在则代表该元素为两数组的交集元素

1.2 代码示例🌰

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();for (int i : nums1) {set1.add(i);}Set<Integer> set = new HashSet<>();for (int i : nums2) {if (set1.contains(i)) {set.add(i);}}int[] ret = new int[set.size()];int k = 0;for (int x : set) {ret[k++] = x;}return ret;}
}

2.两个集合的交集问题II(LeetCode 350)

【题目链接】350. 两个数组的交集 II - 力扣（LeetCode）

2.1 思路分析🎯

这道题可以通过哈希表来解决问题，不过关键在于抓住题目的一个要求：返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致如果出现次数不一致，则考虑取较小值；

将nums1中的数据映射到map中后，遍历nums2，nums2中每个数据只要遍历到了都要到map中进行判断，只要nums2遍历完，出现次数相等 和 取较小值(map.get(n) > 0，map中的数据被遍历完而nums2还有数据也无法加入，表示取两个数组中出现次数的最小值)的情况都能够被覆盖到

2.2 代码示例🌰

class Solution {public int[] intersect(int[] nums1, int[] nums2) {Map<Integer, Integer> map = new HashMap<>();for (int x : nums1) {map.put(x, map.getOrDefault(x, 0) + 1);}int[] ret = new int[nums2.length];int index = 0;for (int n : nums2) {if (map.containsKey(n) && map.get(n) > 0) {ret[index++] = n;map.put(n, map.get(n) - 1);}}return Arrays.copyOfRange(ret, 0, index);}
}