LeetCode 面试题 01.01. 判定字符是否唯一

2023-07-20 HGNULB 约 8 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 简单未解决 2-5 字节跳动程序员面试金典（第 6 版）

题目描述

✅ 面试题 01.01. 判定字符是否唯一

题意分析

问的是一个字符串里的字符是不是两两不同：只要有任意一个字符出现了两次及以上就返回 false，否则返回 true。注意判定对象是「字符」而不是「子串」，也不关心字符的位置或顺序，只关心出现次数有没有超过一次。

约束信号有两条。其一，字符串长度很小（不超过一百），意味着即使写平方级的两两比较也能过，但题目附带了一句「不使用额外的数据结构」的进阶要求，这才是它被当作面试题的原因——它想逼你把「见过哪些字符」这件事压缩到常数空间里。其二，字符取自有限的字符集（ASCII 范围内），有限字符集是所有「定长桶」和「位图」技巧成立的前提。

边界要点清楚：空字符串没有任何重复，应该返回 true；长度为 1 的串同理返回 true；另外由抽屉原理，一旦字符串长度超过字符集大小，必然存在重复，这条可以当成提前退出的捷径。

解法：布尔数组计数

核心思路

最直接的做法是双重循环两两比较，对每个下标 $i$ 去看它后面有没有相同字符，时间 $O(n^2)$。它的浪费在于：为了判断当前字符是不是新的，把之前所有字符又扫了一遍，而「之前出现过哪些字符」这件事本可以一次记下来反复用。

关键观察是字符集有限。既然字符最多只有 128 种，就不需要保存字符串本身，只需要一张 128 格的表记录「这个字符出现过没有」。查表和写表都是 $O(1)$，整体降到一趟扫描。

于是维护这条不变量：扫描进行到下标 $i$ 时，seen 中值为 true 的位置，恰好是 astr[0..i-1] 中出现过的全部字符，一个不多一个不少。 有了它，判定就变成一句话——如果当前字符在 seen 中已经是 true，说明它在前缀里出现过，重复成立，立刻返回 false；否则把它置为 true，不变量在下标 $i+1$ 处继续保持。

顺序很关键：必须先查后写。若反过来先把当前字符写进表再查，那么每个字符都会撞上自己刚写下的记录，函数永远返回 false。整趟扫完都没撞上，说明没有任何字符出现两次，返回 true。

如果要满足「不使用额外数据结构」的进阶要求，把这张布尔表换成一个整数的二进制位即可：第 $k$ 位为 1 表示第 $k$ 个字符出现过，查表变成 mask >> k & 1，写表变成 mask |= 1 << k。逻辑与不变量完全不变，只是把 128 个布尔值折叠成了若干个整数的比特。

解题步骤

开一张长度为 128 的布尔数组 seen，全部初始化为 false。为什么是 128：覆盖整个 ASCII 范围，这样即使输入包含数字、符号或大写字母也不会越界；若题目明确只有小写字母，可以缩到 26 并用 ch - 'a' 做下标。

从左到右遍历字符串，取出当前字符 ch，直接用它的码点当下标。为什么可以直接当下标：字符在语言层面就是整数，省掉哈希计算，查表是真正的常数时间。

先判断 seen[ch] 是否为 true，是则立即返回 false。为什么可以立刻返回：不变量保证 true 只可能由前缀中的同一字符写下，撞上即证明重复，无需继续扫描。

若为 false，把 seen[ch] 置为 true 再进入下一轮。为什么写在判断之后：先写会让当前字符和自己比对，导致函数对任何非空输入都返回 false。

循环正常结束时返回 true。为什么这是对的：能走到这里说明每一个字符在被访问时都不在前缀集合里，即所有字符两两不同；空串一次循环都不进，直接返回 true，与题意一致。

以 astr = "leetcode" 走一遍：seen 初始全 false。$i=0$ 读到 l（码点 108），seen[108] 为 false，置为 true，此时集合是 ${l}$。$i=1$ 读到 e（码点 101），seen[101] 为 false，置为 true，集合是 ${l,e}$。$i=2$ 又读到 e，seen[101] 已经是 true，命中重复，立即返回 false，后面的 t、c、o、d、e 一个都不用看。

再看一组返回真的输入 astr = "abc"：$i=0$ 写下 a（97），集合 ${a}$；$i=1$ 读到 b（98），未命中，写下后集合 ${a,b}$；$i=2$ 读到 c（99），未命中，写下后集合 ${a,b,c}$。循环自然结束，返回 true。

代码实现

// 遍历字符串，若发现已出现则返回 false。
class Solution {
    public boolean isUnique(String astr) {
        boolean[] seen = new boolean[128];
        for (int i = 0; i < astr.length(); i++) {
            char ch = astr.charAt(i);
            if (seen[ch]) {
                return false;
            }
            seen[ch] = true;
        }
        return true;
    }
}

// 遍历字符串，若发现已出现则返回 false。
func isUnique(astr string) bool {
    seen := make([]bool, 128)
    for i := 0; i < len(astr); i++ {
        ch := astr[i]
        if seen[ch] {
            return false
        }
        seen[ch] = true
    }
    return true
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是字符串长度。凭据：只做一趟从左到右的扫描，每个字符对应一次数组读和至多一次数组写，都是常数代价；命中重复时提前返回只会更快。

空间复杂度：$O(1)$，凭据：seen 的长度固定为字符集大小 128，与输入长度无关，是个常数；若改用位图写法则进一步压成几个整数变量。

关键点总结

「字符集有限」是把哈希表降级成定长数组的通行证。只要键的取值范围是常数级的，就该用数组直接寻址而不是 HashSet，省掉哈希计算和装箱开销，空间也从 $O(n)$ 变成 $O(1)$。

先查后写的顺序不是风格问题而是正确性问题。凡是「当前元素与历史元素配对」的题（两数之和、最长无重复子串都属此类），都要先明确当前元素能不能和自己配对，再决定查写次序。

把不变量写成一句话：「表中为真的位置恰是已扫描前缀的字符集合」。有了它，提前返回的正确性、循环结束返回真的正确性都能一句话说清，不用靠举例试探。

布尔数组和位图是同一个思想的两种实现，后者只是把每个布尔值压进一个比特。看到「不使用额外数据结构」「常数空间」这类要求，就往位图方向想。

面试视角：这题的分水岭是进阶要求。只写出布尔数组是及格线，能主动把它改写成整型位图并说清 mask >> k & 1 与 mask |= 1 << k 的含义，才是面试官想看到的答案。

面试视角：值得主动提一句抽屉原理——若字符串长度超过字符集大小就必然有重复，可以在循环前一行返回。它体现的是「先用数学结论砍掉一整类输入」的意识，在很多计数题里都能复用。

易错点总结

错误写法：先写后查，即 seen[ch] = true; 写在 if (seen[ch]) 之前。用例 "abc" → 第一个字符 a 刚被标记就立刻被自己命中，函数对任何非空串都返回 false。

错误写法：数组开成长度 26 并用 ch - 'a' 做下标，却没有确认输入只含小写字母。用例 "aA" → 大写 A 的偏移量是 $-32$，直接数组越界抛异常。

错误写法：数组开成长度 128 却直接用未经检查的字符码点索引。用例含有中文或其他非 ASCII 字符的串 → 码点远大于 127，越界崩溃；这类输入下必须换用哈希集合或扩大表长。

错误写法：空串返回 false，理由是「没有字符可比较」。用例 "" → 空串不含任何重复字符，正确答案是 true，这是最容易被漏掉的边界。

错误写法：位图写法里用 32 位整数承载 128 个字符的标记。用例 "a"（码点 97）→ 1 << 97 在 Java 里移位数按 32 取模变成 1 << 1，标记落到了完全无关的位上，判定结果随机出错。

错误写法：位图判定写成 if ((mask & (1 << k)) == 1)。用例任何 $k>0$ 的字符 → 与运算的结果是 $2^k$ 而不是 1，条件恒假，重复永远检测不出来；正确写法是与 0 比较或先右移再与 1。

错误写法：写双重循环但内层从 0 开始且不跳过 j == i。用例 "abc" → 每个字符都会和自己相等，立刻返回 false；内层必须从 $i+1$ 起或显式跳过自身。

错误写法：改用排序后比较相邻字符，却忘了原串在部分语言中不可变，直接在原对象上排序。用例任意输入 → 在 Java 中 String 无法原地排序，需要先转成字符数组；而且排序把时间抬到 $O(n\log n)$，比一趟扫描更差。

错误写法：用集合时只做 contains 判断却忘了把当前字符 add 进去。用例 "aa" → 集合始终为空，两次查询都未命中，返回 true，漏判重复。

错误写法：把「字符唯一」误解成「相邻字符不同」，只比较 astr[i] 与 astr[i-1]。用例 "aba" → 相邻位置都不相同，返回 true，但字符 a 实际出现了两次，正确答案是 false。

相似题目

题目	难度	考察点
49. 字母异位词分组	中等	把计数表本身当作哈希键做分组
242. 有效的字母异位词	简单	一加一减复用同一张计数表
383. 赎金信	简单	判定的是包含关系而非相等，需比较次数上限
387. 字符串中的第一个唯一字符	简单	要记录次数而不只是出现过，且需二次扫描定位
451. 根据字符出现频率排序	中等	统计之后还要按频次排序并重建字符串
LCR 032. 有效的字母异位词	简单	额外要求两串完全相同时判为不成立
LCR 033. 字母异位词分组	中等	分组换皮题，练习计数签名的序列化方式
剑指 Offer 50. 第一个只出现一次的字符	简单	空串要返回特定占位字符，边界约定不同
面试题 01.02. 判定是否互为字符重排	简单	先比长度再比计数，两串之间的对照
面试题 01.04. 回文排列	简单	判定奇数次字符至多一个，可用异或位图压缩
面试题 10.02. 变位词组	中等	变位词分组换皮，可对比排序键与计数键的取舍