代码随想录二刷-哈希表-两个数组的交集(JS)

349.两个数组的交集

题目

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：

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

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

方法

抓住本题特性不能有重复元素，所以我们选择Set数据结构

将其中一个数组全都加入Set中

（也可以直接创建包含该数组的set）

然后遍历另一个数组，如果set中含有该数组的元素，就将该元素加入到一个新的reset中

最后将reset转化为数组

代码

/* @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersection = function(nums1, nums2) {let set = new Set();let reSet = new Set();// 1.可以直接创建时加入// let set = new Set(nums1);// 2.循环比迭代器快for (let num of nums1){set.add(num);}for (let num of nums2){if (set.has(num)){reSet.add(num);}}return Array.from(reSet);
};

350.两个数组的交集 II

题目

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：

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

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

方法

1.使用Map解决

我的方法：

先将nums1和nums2分别存入Map中，然后遍历nums1Map，如果nums1Map中的key在num2Map中存在，取两者的最小value，加入最小value次这个key

【我的方法绕了一些圈子】

别人的方法：

还可以使用map来解决，具体操作如下

遍历nums1中的所有元素，把它存放到map中，其中key就是nums1中的元素，value就是这个元素在数组nums1中出现的次数。

遍历nums2中的所有元素，查看map中是否包含nums2的元素，如果包含，就把当前值加入到数组中，然后对应的value要减1。

作者：sdwwld

【我的思路的简化】

2.双指针解决

先对两个数组进行排序，然后使用两个指针，分别指向两个数组开始的位置。

如果两个指针指向的值相同，说明这个值是他们的交集，就把这个值加入到数组中，然后两个指针在分别往后移一步。
如果两个指针指向的值不同，那么指向的值相对小的往后移一步，相对大的先不动，然后再比较
一直重复上面的操作，直到其中一个指针不能再移动为止。

作者：sdwwld

代码

我的方法

/* @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersect = function(nums1, nums2) {let nums1Map = new Map();let nums2Map = new Map();let res = new Array();for (let i = 0;i < nums1.length;i++){nums1Map.set(nums1[i],(nums1Map.get(nums1[i]) || 0) + 1);}for (let i = 0;i < nums2.length;i++){nums2Map.set(nums2[i],(nums2Map.get(nums2[i]) || 0) + 1);}for (let x of nums1Map) {if (nums2Map.has(x[0])){let count = Math.min(x[1],nums2Map.get(x[0]));while (count--) {res.push(x[0]);}}}return res;
};

别人的Map方法

/* @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersect = function(nums1, nums2) {let nums1Map = new Map();let res = new Array();for (let i = 0;i < nums1.length;i++){nums1Map.set(nums1[i],(nums1Map.get(nums1[i]) || 0) + 1);}for (let i = 0;i < nums2.length;i++){if (nums1Map.get(nums2[i]) > 0){res.push(nums2[i]);nums1Map.set(nums2[i],nums1Map.get(nums2[i]) - 1);}}return res;
};

其实和用数组存储字母差不多，都是遇到相同的字符 value–

双指针方法

/* @param {number[]} nums1* @param {number[]} nums2* @return {number[]}*/
var intersect = function(nums1, nums2) {let res = new Array();// 划重点！！！！//sort()根据ASCII码进行的比较// 如果不传入函数的话，只有个位数的比较是正确的nums1.sort((a,b) => a - b);nums2.sort((a,b) => a - b);let one = two = 0;while (one < nums1.length && two < nums2.length){if (nums1[one] == nums2[two]){res.push(nums1[one]);one++;two++;} else if (nums1[one] > nums2[two]) {two++;} else {one++;}}return res;
};