C++字符串拼接st=st+b与st+=b触发LeetCode TLE差异原因咨询

你遇到的超时问题本质是两种写法底层执行逻辑完全不同，性能差距巨大：

• st = st + b 首先调用std::string的operator+重载，该操作会创建一个全新的临时字符串对象，内存大小为原st长度+1，将原st的所有字符和字符b拷贝到新内存后，再将临时对象赋值给原st，同时释放原st的旧内存。
  在内层循环逐字符拼接的场景下，这种写法的总时间复杂度是O(n²)，n为最终字符串长度：每次拼接都要拷贝当前所有已存在的字符，总拷贝次数为1+2+...+n = n(n+1)/2，当输入规模较大时必然触发超时。
• st += b 调用的是std::string的operator+=重载，该操作直接在原st的内存空间上修改：只要当前st预分配的容量足够容纳新字符，仅需O(1)时间完成写入；就算容量不足需要扩容，std::string默认采用2倍或1.5倍的成倍扩容策略，总拷贝次数依然是O(n)级别，性能远高于前者。

• 编译优化限制：部分编译器在开启高等级优化（如O2）时可能会将st = st + b的临时对象创建逻辑优化掉，等价于+=的执行效果，但LeetCode的默认编译配置通常不会开启这类强优化，因此原生写法的性能差异会直接体现。
• 未预分配内存：你的场景中最终输出字符串的长度和输入字符串s的长度完全一致，可以在初始化st后调用st.reserve(s.size())提前预分配足额内存，完全避免拼接过程中的扩容开销，性能会进一步提升。

你代码中的内层逐字符循环可以直接替换为append批量拼接，完全省去内层循环开销：

string frequencySort(string s) {
    priority_queue<pair<int,char>> pq;
    unordered_map<char,int> m;
    for(int i = 0;i<s.size();i++)
        m[s[i]]++;
    for(auto x:m)
        pq.push(make_pair(x.second,x.first));
    string st = "";
    st.reserve(s.size()); // 提前预分配内存
    while(!pq.empty()){
        int x = pq.top().first;
        char b = pq.top().second;
        st.append(x, b); // 批量拼接x个字符b，无需内层循环
        pq.pop();
    }
    return st;
}

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