检查字符串是否由唯一字符组成的最简单方法？

检查字符串是否由唯一字符组成的最简单方法？

我不喜欢1.-这是O（N 2）算法。您的2.大致是线性的，但始终遍历整个字符串。您的3.是O（N lg 2 N），（可能）有一个相对较高的常数-
可能几乎总是比2慢。

但是，我的首选是，当您尝试将字母插入集合中时，检查它是否已经存在，如果已经存在，则可以立即停止。给定字母的随机分布，平均应该只扫描一半的字符串。

编辑：这两个评论都是正确的，您希望扫描的字符串的确切部分将取决于分布和长度-
在某些时候，字符串足够长以至于不可避免的重复，并且（例如）缺少一个字符那个机会仍然很高。实际上，给定平坦的随机分布（即，集合中的所有字符均具有相同的可能性），这应与生日悖论紧密吻合，这意味着发生碰撞的机会与字符中可能出现的字符数的平方根有关。字符集。举例来说，如果我们假设基本US-
ASCII（128个字符）具有相同的概率，则在大约14个字符处发生冲突的可能性为50％。当然，在实际的字符串中，我们可能会比它早一些，因为ASCII字符不是’