哈哈，这个现象其实挺常见的——理论上的时间复杂度优势在极小测试用例里被常数开销盖过去了，我来给你拆解一下具体原因：

核心原因：小数据量下，常数开销主导运行时间 #

你的测试用例里，J只有2个字符，S也才7个字符，这种量级下，算法的渐近复杂度（O(n) vs O(n²)）根本发挥不出作用，反而额外的操作开销会成为主导：

• 解法2里需要额外初始化unordered_set，包括哈希表的内存分配、把J的字符插入集合的操作，这些都是固定的常数开销，在数据量极小的时候，这笔开销比O(1)查找比O(n)查找省下的时间多得多。
• 解法1里的string::find在短字符串上几乎是瞬间完成的——本质就是遍历2个字符做比较，和哈希查找的计算、冲突处理开销比起来，反而更高效。

其他影响因素 #

1. 哈希容器的实际开销
   虽然unordered_set的查找是理论O(1)，但实际中需要计算字符的哈希值，还要处理可能的哈希冲突（哪怕概率极低），这些步骤都有额外开销。对于只有2个元素的集合，线性遍历（string::find）的成本反而更低。
2. 编译器优化的差异
   编译器可能对解法1做了更激进的优化：比如因为你的J是固定的"aA"，编译器会直接把j.find(s1)优化成(s1 == 'a' || s1 == 'A')这种直接的字符比较，而解法2的unordered_set操作因为涉及动态容器，优化空间更小。

怎么验证理论复杂度的优势？ #

你可以试试下面的测试方法，就能看到解法2的真正优势：

• 放大测试用例：把J设成包含所有大小写字母（52个字符），S生成一个100万字符以上的随机字符串，再测试两者的运行时间。
• 多次循环取平均：单次运行的时间误差太大，把函数调用放在一个循环里跑10000次以上，再计算平均耗时，这样结果更可信。

附上你的原始代码参考：

解法1（O(n²)理论复杂度） #

int numJewelsInStones(string j, string s) {
    unordered_map<char, int>stones;
    for(char s1:s) ++stones[s1];
    auto it = stones.begin();
    int count = 0;
    for(it = stones.begin(); it != stones.end(); ++it) {
        char s1 = it->first;
        if(j.find(s1) != string::npos) count += it->second;
    }
    return count;
}

解法2（O(n)理论复杂度） #

int numJewelsInStones(string j, string s) {
    unordered_map<char, int>stones;
    for(char s1:s) ++stones[s1];
    unordered_set<char>uset(j.begin(), j.end());
    auto it = stones.begin();
    int count = 0;
    for(it = stones.begin(); it != stones.end(); ++it) {
        char s1 = it->first;
        if(uset.find(s1) != uset.end()) count += it->second;
    }
    return count;
}

测试代码 #

int main() {
    clock_t tStart = clock();
    Solution ob;
    string j = "aA", s = "aAAbbbb";
    cout << ob.numJewelsInStones(j, s) << endl;
    cout << (double)(clock() - tStart)/CLOCKS_PER_SEC;
    cout << endl;
    return 0;
}

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