(哈希表 ) 349. 两个数组的交集 ——【Leetcode每日一题】

❓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

💡思路：

法一：排序+双指针

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

• 首先对两个数组进行排序；
• 然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的；
• 为了保证加入元素的唯一性，我们在向结果数组ans 添加元素时，要判断该元素是否已经存在（如果ans添加第一个元素时，不需要判断）。

法二：哈希表

输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的，根据哈希表的性质可以去重：

• 首先将 num1 中的元素放到哈希表 s1 中；
• 然后遍历 num2 中元素，如果 s1 中也存在，则保存到另一个哈希表 ans 中;
• 最后哈希表 ans 就是所求交集，将结果集合转为数组。

🍁代码：(Java、C++)

法一：排序+双指针
Java

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int len1 = nums1.length, len2 = nums2.length;int[] ans = new int[Math.min(len1, len2)];int index1 = 0, index2 = 0, index = 0;while(index1 < len1 && index2 < len2){if(nums1[index1] == nums2[index2]){if(index == 0){ans[index++] = nums1[index1];}else if(nums1[index1] != ans[index - 1]){ans[index++] = nums1[index1];}index1++;index2++;}else if(nums1[index1] < nums2[index2]){index1++;}else{index2++;}}return Arrays.copyOfRange(ans, 0, index);}
}

C++

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());vector<int> ans;vector<int>::iterator ite1 = nums1.begin(), ite2 = nums2.begin();while(ite1 != nums1.end() && ite2 != nums2.end()){if(*ite1 == *ite2){if(ans.size() == 0){ans.push_back(*ite1);}else if(*ite1 != ans.back()){ans.push_back(*ite1);}ite1++;ite2++;}else if(*ite1 < *ite2){ite1++;}else{ite2++;}}return ans;}
};

法二：哈希表
Java

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> s1 = new HashSet<Integer>();Set<Integer> ans = new HashSet<Integer>();for(int num : nums1){s1.add(num);}for(int num: nums2){if(s1.contains(num)){ans.add(num);}}//将结果集合转为数组, 另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[ans.size()];int j = 0;for(int i : ans){arr[j++] = i;}return arr;}
}

C++

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> s(nums1.begin(), nums1.end());unordered_set<int> ans;for(int num : nums2){if(s.find(num) != s.end()){ans.insert(num);}}return vector<int>(ans.begin(), ans.end());;}
};

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：法一：$O(mlogm+nlogn)$，其中 m 和 n 分别是两个数组的长度。对两个数组排序的时间复杂度分别是 $O(m\log m)$ 和 $O(n\log n)$，双指针寻找交集元素的时间复杂度是 $O(m+n)$。法二为：$O(m+n)$。
• 空间复杂度：法一：$O(logm+logn)$，其中 m 和 n 分别是两个数组的长度 , 空间复杂度主要取决于排序使用的额外空间。法二为：$O(n)$， n 为两数组长度的最小值。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！

注： 如有不足，欢迎指正！