C++中能否用vector<int>作为map的键？附LeetCode实践代码

核心问题解答 #

可以用vector<int>作为map的键，C++标准库为vector提供了默认的<比较运算符（按字典序逐个元素比较），完全满足map对键的可比较要求，所以map<vector<int>, vector<int>>、map<vector<int>, vector<vector<int>>>这类定义都是合法且可正常使用的。

你的代码问题分析 #

你给出的代码逻辑思路是对的，但存在一个关键疏漏：生成差值向量v后，没有将其与对应的字符串存入map。循环中只完成了v的构建，缺少m[v].push_back(i);这一步，导致map始终为空，自然无法找到符合条件的元素返回。

修正后的代码 #

class Solution {
public:
    string oddString(vector<string>& words) {
        map <vector<int>,vector<string>> m;
        for(auto i:words)
        {
            vector<int> v;
            for(int j=1;j<i.size();j++)
            {
                v.push_back(int(i[j]-i[j-1]));
            }
            m[v].push_back(i); // 补上这行，建立差值向量与字符串的关联
        }
        for(auto &i:m) // 加引用避免不必要的拷贝，提升效率
        {
            if(i.second.size() == 1)
            {
                return i.second[0];
            }
        }
        return "";
    }
};

额外优化提示 #

如果想要更高的运行效率，可以考虑使用unordered_map替代map，但标准库没有为vector<int>提供默认的哈希函数，需要自行实现；而map依赖比较运算符，使用起来更省心，完全适配本题的数据规模。

内容的提问来源于stack exchange，提问作者KESHAV MAHESHWARI