(哈希表 ) 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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

法二：哈希表
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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());;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：法一：$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—力扣专栏，每日更新！

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