题目

给定两个数组 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

题解

假设这道题没有给元素大小在0~1000中，那么set是最优解。因为给的元素跨度可能很大，0，99999。这样的话用数组来存储就很浪费空间了。我们先假设没有给元素范围。

思路是：先用nums1初始化set，保证set中元素唯一。再for循环遍历nums2中各个元素，看元素是否在set中，若在则存放在保存结果的set中。为什么结果先用set存储，因为要保证交集元素不重复，若这时直接用vector存储，则后面再来一个一样的元素就会发生错误。之后再用结果set初始化vector,返回vector。

时间复杂度O(nlogn)

空间复杂度O(n)

vector<int> intersection_1(vector<int>& nums1, vector<int>& nums2) {
        set<int> result;
        set<int> temp1(nums1.begin(),nums1.end());
        for(int num2:nums2){
            if(temp1.find(num2)!=temp1.end()){
                result.insert(num2);
            }
        }
        vector<int>result1(result.begin(),result.end());
        return result1;
    }

这时再按题目给了元素大小0~1000解。这样就能用数组解，比较方便。数组大小为1001，初始化为0.nums1中元素遍历时+1,nums2中遍历时若对应元素不为0，则加入set中。最后set再转换成vector。

 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> result;
        int hash[1001]={0};
        for(int num1:nums1) {
            hash[num1]++;
        }
        for(int num2:nums2){
           if(hash[num2]!=0){
               result.insert(num2);
           }
        }
        vector<int>result1(result.begin(),result.end());
        return result1;
    }

总结

set使用范围是，要求元素不重复出现，同时元素直接跨度很大的情况(0,9999,6,22222)。而使用数组做哈希一般是题目限制了输入的范围比如这题中限制输入为0~1000，这种情况下用数组就很好了。用map的情况是，我们不仅要知道哈希表中有无对应元素，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。到底使用key:value,还是value:key由最后输出决定，若要求返回索引则map为<元素,下标>,若要求返回元素，说实话不用map都行，直接set，若set中有所查找元素返回查找到的元素和当前遍历元素。