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

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

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

以上便是对两个集合的交集问题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨