力扣2085题解析：统计两个数组中只出现一次的公共单词数目详解
一、题目解读
力扣2085题要求给定两个字符串数组words1和words2，统计两个数组中只出现一次的公共单词的数量。例如，若words1包含["a", "b", "c", "c"]，words2包含["c", "d", "e", "e"]，则公共单词仅有"c"且仅各出现一次，答案为1。题目关键在于识别单次出现的公共元素，需高效处理重复与交集问题。
二、解题思路
采用哈希表统计 + 交集计算的策略，核心思路分为三步：
1. 使用unordered_map分别统计words1和words2中每个单词的出现次数；
2. 筛选两个数组中仅出现一次的单词，存入unordered_set（利用集合的唯一性）；
3. 遍历其中一个集合，检查另一个集合是否存在该单词，计数交集大小。
此解法巧妙利用哈希表O(1)的查询优势，避免重复遍历，时间复杂度优化至O(n)。
三、解题步骤
1. 统计单词频次：创建count1和count2，循环遍历words1和words2，用哈希表记录每个单词的出现次数（如count1["a"]++）。
2. 筛选单次单词：遍历count1和count2，仅当次数为1时（cnt == 1），将单词加入once1和once2集合。
3. 计算交集数量：遍历once1，若once2中存在相同单词（once2.count(word)），则结果result++。
此步骤通过集合的快速查找（O(1)）实现交集统计，降低复杂度。
四、代码及注释
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
int countWords(vector<string>& words1, vector<string>& words2) {
// 统计words1中每个单词的出现次数
unordered_map<string, int> count1;
for (const string& word : words1) { // 利用引用避免复制
count1[word]++; // 频次累加
}
// 统计words2中每个单词的出现次数
unordered_map<string, int> count2;
for (const string& word : words2) {
count2[word]++;
}
// 收集words1中只出现一次的单词
unordered_set<string> once1;
for (const auto& [word, cnt] : count1) { // C++17结构化绑定
if (cnt == 1) {
once1.insert(word); // 加入集合
}
}
// 收集words2中只出现一次的单词
unordered_set<string> once2;
for (const auto& [word, cnt] : count2) {
if (cnt == 1) {
once2.insert(word);
}
}
// 计算两个集合的交集大小
int result = 0;
for (const string& word : once1) {
if (once2.count(word)) { // 判断是否存在于once2
result++; // 交集计数
}
}
return result;
}
};注释说明：
● 使用哈希表（unordered_map）高效统计频次；
● 利用unordered_set存储单次单词，避免重复判断；
● 交集计算通过count(word)方法实现快速查找。
五、总结
本解法通过哈希表与集合的组合，将时间复杂度优化至线性级别，适用于大规模数据场景。关键点在于：
1. 频次统计为后续筛选提供基础；
2. 集合的交集查找取代双重遍历，提升效率。
原创内容 转载请注明出处
