language-agnostic - 在 O(n) 时间和 O(1) 内存中检测字符串中是否存在重复项并且没有数据结构

Question

问题是要弄清楚给定字符串中是否没有任何重复的字符。约束是字符串仅包含字符 az（仅小写）。

显而易见的解决方案是使用数组（或哈希表）来跟踪您遇到的字符。但问题是你不能使用数据结构。

以下是该问题的一种解决方案。但我不太明白它是如何工作的。我可以看到它使用整数的位来跟踪遇到的字符。

public boolean isUniqueChars(String str) {
    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;
}

Answer 1

您是正确的，因为它为每个字母设置了位。但它首先检查（使用按位与），如果它已经找到当前字母，则它知道该字符串不包含唯一字母。

Answer 2

我会尽力解释。 int checker;是 32 位表示。因为 az 总共有 26 个字母，所以 32 位（1 个整数类型数据）足以标记使用的字符。 checker |= (1 << val);用于标记 az 字符已被使用。也许它可以帮助你:)