【题解】NowCoder NC313 两个数组的交集

题目来源：牛客

NC313 两个数组的交集

题目描述

给定两个整数数组分别为 nums1 ， nums2 ，找到他们的公共元素并返回。
数据范围：1 ≤ nums1.length ， nums2.length ≤ 1000
1 ≤ nums1[i] ， nums2[i] ≤ 1000

示例1

输入： [1,2] , [2,2,2,2]
返回值：[2]
说明： 两个数组的公共元素只有 2

示例2

输入： [1,2,3] , [8,2,2,3,8]
返回值：[2,3]
说明： 两个数组的公共元素为 2 和 3 ，返回 [3,2] 也是一个正确答案

解析

这个题稍微有点歧义，公共元素还是很容易找到，但是，假如两个数组里都含有两个 2 ，那么公共元素到底有几个 2 呢，这题目并没有说清楚，但在这题里，多个 2 只算做一个。
这题思路很简单，遍历第一个数组，将第一个数组拥有的元素标记一下，在遍历第二个数组，若是第二数组标记的元素已经被第一个数组标记过，那么这个数就是公共元素。

如图，被两次标记的元素就是公共元素。用容器哈希表来标记肯定是小题大做了，逻辑简单，我们使用数组模拟即可。

代码实现

本体是接口型，只需要把答案返回即可。

class Solution
{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
    	// 哈希数组，记录数字是否在nums1中出现
        bool hash[1010] = { 0 };
        // 将答案存到ret中
        vector<int> ret;
        // 遍历nums1，将里面的元素存放到hash数组中
        for (auto e : nums1)
        {
        	// 出现过则标记为true
            hash[e] = true;
        }
        // 遍历nums2
        for (auto e : nums2)
        {
        	// 如果该值在hash数组中为真，说明该数字是公共数字
            if (hash[e])
            {
             	// 将该数字存到ret中
                ret.push_back(e);
                // 避免重复存入同一个数字，需要在hash数组中去除该值
                hash[e] = false;
            }
        }
        // 返回答案
        return ret;
    }
};