350. 两个数组的交集 II
#数组#哈希表 2025-01-15 
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
26
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums2.size() > nums1.size()){
            swap(nums1,nums2);
        }

        // 先把元素加入到 链表中
        vector<int> result;
        list<int> find_list;
        for (const auto& num : nums1) {
            find_list.push_back(num);
        }
        
        // 如果找到就加入 vector 中，并且从链表中移除
        for (const auto& num : nums2) {
            auto it = std::find(find_list.begin(), find_list.end(), num);
            if(it != find_list.end()){
                result.push_back(num);
                find_list.erase(it);
            }
        }

        return result;
    }
};

先要保证 加入元素到链表中的数组是元素最多的，通过 swap 交换来保证。

之所以选择链表，而没有选择 set，因为后者会进行去重，导致统计结果有问题。

如果在 find_list 找到，就说明当前元素就是交集之一，加入 result，还要记得把 find_list 中该元素移除。重复这个操作，最终得到想要的数据。