同为O(N)时间复杂度的计数排序代码为何一个触发超时（TLE）错误另一个却正常运行？

这问题其实挺典型的，很多刚接触Java字符串操作的同学都会踩这个坑！两段代码的核心计数排序逻辑完全一致，差异只出在最后将结果char数组转换为String的环节，正是这个细节导致了性能天差地别：

核心差异分析 #

先看两段代码的结尾部分：

代码1的字符串拼接方式 #

for(int i=0;i<a.length;i++) { 
    ans+=a[i]; 
}
return ans;

代码2的字符串构建方式 #

return new String(a);

为什么代码1会超时？ #

Java的String是不可变对象，每执行一次ans += a[i]，本质上都会创建一个全新的String对象：它需要把原来ans中的所有字符，和当前的a[i]一起复制到新的内存空间里。假设输入字符串长度为N，这个循环的总操作次数是1+2+3+...+N = N(N+1)/2，时间复杂度直接从预期的O(N)变成了O(N²)。当输入规模较大（比如十万级以上的字符数），这种低效的拼接就会触发超时错误。

为什么代码2能正常执行？ #

new String(a)是Java String类提供的原生构造方法，它会直接一次性将char数组的内容拷贝到字符串的底层存储结构中，整个操作的时间复杂度是严格的O(N)，完全符合计数排序预期的线性时间复杂度，所以能高效处理大规模输入。

总结 #

两段代码的计数排序核心逻辑都是O(N)，但代码1的字符串拼接环节偷偷把整体时间复杂度拉高到了O(N²)，这就是导致超时的根本原因。如果要在Java中高效拼接字符串，除了直接用char数组构造外，还可以使用StringBuilder来避免频繁创建新对象。

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