检测字符串是否包含唯一字符：将我的解决方案与“破解编码面试？”进行比较

检测字符串是否包含唯一字符：将我的解决方案与“破解编码面试？”进行比较

这里有两个独立的问题：您的解决方案的效率是多少，参考解决方案的作用是什么？让我们独立对待每个人。

首先，您的解决方案：

public static boolean checkForUnique(String str){    boolean containsUnique = false;    for(char c : str.toCharArray()){        if(str.indexOf(c) == str.lastIndexOf(c)){ containsUnique = true;        } else { containsUnique = false;        }    }    return containsUnique;}

您的解决方案实质上是由一个遍历字符串中所有字符的循环组成（假设有n个字符），并在每次迭代中检查字符的第一个索引和最后一个索引是否相同。该

indexOf

和

lastIndexOf

方法都需要时间为O（n），因为他们有所有扫描字符串的字符，以确定其中是否匹配你要找的人。因此，由于循环运行O（n）次并且O（n）每次迭代都起作用，因此其运行时间为O（n
2）。

但是，您的代码有些疑惑。尝试在字符串上运行它

aab

。在此输入上可以正常工作吗？提示一下，一旦确定有两个或多个重复的字符，就可以保证有重复的字符，并且可以返回并非所有字符都是唯一的。

现在，让我们看一下参考：

public static boolean isUniqueChars(String str) {    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?        return false;    }    int checker = 0;    for (int i = 0; i < str.length(); i++) {        int val = str.charAt(i) - 'a';        if ((checker & (1 << val)) > 0) return false;        checker |= (1 << val);    }    return true;}

这个解决方案很可爱。基本思想如下：假设您有一个由26个布尔值组成的数组，每个布尔值都跟踪字符串中是否已经出现了特定字符。您从所有错误开始。然后，您遍历字符串的字符，并且每次看到字符时，都会在该字符的数组插槽中查看。如果是的话

false

，这是您第一次看到该角色，可以将广告位设置为

true

。如果是

true

，则您已经看过此字符，您可以立即报告有重复的字符。

注意，此方法不分配布尔数组。相反，它选择了一个巧妙的把戏。由于只能存在26个不同的字符，并且中有32位

int

，因此该解决方案创建了一个

int

变量，其中变量的每一位都对应于字符串中的一个字符。该解决方案不读取和写入数组，而是读取和写入数字的位。

例如，看下面这行：

if ((checker & (1 << val)) > 0) return false;

怎么

checker & (1 << val)

办？好吧，

1 <<val

创建一个

int

除

val

第th位外所有位均为零的值。然后，它使用按位AND将该值与进行与

checker

。如果位置

val

in
的位

checker

已设置，则该值将为非零值（表示我们已经看过该数字），并且可以返回false。否则，它的值为0，我们还没有看到这个数字。

下一行是这样的：

checker |= (1 << val);

这使用“按位或与赋值”运算符，等效于

checker = checker | (1 << val);

该OR

checker

的值仅在position处设置了1位

val

，从而将其打开。等同于将数字的

val

第一位设置为1。

这种方法比您的方法快得多。首先，由于该函数通过检查字符串的长度是否大于26（我假设256是一个错字）而开始，因此该函数从不必测试任何长度为27或更大的字符串。因此，内部循环最多运行26次。每次迭代确实在位运算O（1）工作，所以做了整体的工作是O（1）（O（1）次迭代O（1）每次迭代工作），这是
显著 比你更快地实现。

如果您还没有看到以这种方式使用按位运算，我建议您在Google上搜索“按位运算符”以了解更多信息。

希望这可以帮助！