是否唯一

指令

创建一个函数，判断字符串中的所有字符是否都唯一。该函数需区分大小写，即同时包含 'a' 和 'A' 的字符串仍可通过测试。

输入：字符串
输出：布尔值

示例

1isUnique('abcdef'); // -> true
2isUnique('89%df#$^a&x'); // -> true
3isUnique('abcAdef'); // -> true
4isUnique('abcaef'); // -> false

我们立即意识到，必须处理字符串中的每一个字符。此算法的最佳时间复杂度为线性，即 O(n)。这是无法避免的。

---

1function isUnique(str) {
2    // 你的代码在此
3}

---

解法 1

这是最直接、暴力的解法。

1function isUnique(str) {
2    for(let i = 0; i < str.length; i++) {
3        if(str.lastIndexOf(str[i]) !== i) {
4            return false;
5        }
6    }
7  
8    return true;
9}

工作原理

我们遍历整个字符串。对于每个字符，检查其最后一次出现的位置是否与当前循环索引相同。

如果检查失败，说明该字符在后续位置再次出现，可立即返回 false。若遍历完成，说明所有字符均唯一，返回 true。

时间复杂度

外层循环遍历字符串中每个字符，初始复杂度为 O(n)。

内层 str.lastIndexOf() 从后往前扫描字符串。当处理第一个字符时，若所有字符唯一，则需遍历整个字符串。

随着循环推进，lastIndexOf 需要扫描的字符数逐渐减少。平均而言，每次调用需扫描字符串一半长度，因此 lastIndexOf 的时间复杂度为 O(1/2 * n)，去掉常数后为 O(n)。

由于 lastIndexOf 嵌套在循环内部，时间复杂度相乘，最终结果为：

O(n²)

空间复杂度

无论字符串多长，函数中仅使用一个变量 i，因此空间复杂度为：

O(1)

这是可达到的最佳空间复杂度。

但时间复杂度仍有优化空间。

---

解法 2

1function isUnique(str) {
2    const chars = str.split('').sort();
3
4    for(let i = 1; i < chars.length; i++) {
5        if(chars[i] === chars[i - 1]) {
6            return false;
7        }
8    }
9    
10    return true;
11}

工作原理

将字符串中每个字符放入数组并排序。排序后，重复字符会相邻排列。

然后遍历排序后的数组，检查当前字符是否与前一个字符相同。若相同则返回 false。若遍历完成，说明所有字符唯一，返回 true。

时间复杂度

排序算法的时间复杂度约为 O(n * log(n))。循环部分为 O(n)。

两者独立执行，总时间复杂度为 O(n + n * log(n))。去掉低阶项后为：

O(n * log(n))

这是最终的时间复杂度。

空间复杂度

需要存储所有字符到数组中，因此空间复杂度为：

O(n)

我们可以做得更好。

---

解法 3

1function isUnique(str) {
2    const chars = {};
3  
4    for(let i = 0; i < str.length; i++) {
5        const thisChar = str[i];
6    
7        if(chars[thisChar]) {
8            return false;
9        }
10
11        chars[thisChar] = true;
12    }
13
14    return true;
15}

工作原理

在循环中逐个处理字符，并将其存入对象中，以记录已遇到的字符。

每处理一个字符，检查对象中是否已存在该字符。若存在，返回 false；否则将其加入对象，继续下一次迭代。遍历完成后，说明所有字符唯一，返回 true。

时间复杂度

外层循环为 O(n)。

循环内部的操作均为 O(1)：无嵌套循环或类似循环的函数。JavaScript 中对象的插入和查找通常为 O(1)，因为它们本质上类似于哈希表。

因此，最终时间复杂度为：

O(n)

空间复杂度

我们为每个遇到的字符创建一条记录，因此空间复杂度为：

O(n)

使用的空间与输入大小成正比。

---

优化改进

我们可以对上述解法进行微调，使其更优雅。不再使用对象，而是使用 ES2015 新增的数据结构——Set。

Set 与对象类似，用于存储项目并稍后检索。

Set 的主要优势在于：它只能存储唯一的值。尝试添加重复项会被静默忽略，只保留唯一值。

此外，Set 支持快速插入和查找。

1function isUnique(str) {
2    const chars = new Set();
3  
4    for(let i = 0; i < str.length; i++) {
5        const thisChar = str[i];
6    
7        if(chars.has(thisChar)) {
8            return false;
9        }
10
11        chars.add(thisChar);
12    }
13
14    return true;
15}

我认为这个版本更优雅，因为它使用了 Set 这一数据结构，正是其设计用途。方法名 has 和 add 含义清晰，整体代码更易理解。

---

令人惊讶的是，Set 还能让我们将代码简化为一行。这是“巧妙”的解法，但效率略低于解法 3。

解法 4

1function isUnique(str) {
2    return new Set(str).size === str.length;
3}

如果所有字符唯一，集合的大小等于字符串长度；若有重复字符，集合大小会小于字符串长度，因为重复项被自动忽略。

虽然此解法的时间和空间复杂度也都是 O(n)，但通常比解法 3 稍慢。因为解法 3 在发现重复字符时可以提前终止循环，而此解法必须遍历完整个字符串才能得出结果。

---

数组支持

值得一提的是，解法 4 以及解法 3 的两个版本（使用对象的版本和使用 Set 的版本）不仅适用于字符串，也适用于数组。不信？可以自己动手验证一下。

1function isUnique(str) {
2    return new Set(str).size === str.length;
3}

字符串和数组都是可迭代对象，Set 对它们的处理方式一致。

---

总结

暴力解法

第一种解法是大多数人最先想到的，简单直接。若你能识别出时间复杂度并进一步优化，便能在面试中脱颖而出。

第二种解法提升了时间效率，但牺牲了空间。

理想解法

第三种解法展示了合适数据结构如何显著降低时间复杂度。通过引入对象或 Set，我们将原本 O(n * log(n)) 的解法优化为 O(n)，提升明显。

尽管第四种解法巧妙且简洁，但效率不如第三种。不过在面试中，它仍是极佳的答案。

代码扩展性

最后一个解法同时适用于字符串和数组，说明我们的解决方案很容易适配其他输入类型。在本课程的许多问题中，只需做少量调整即可复用。

掌握这些解题技巧才是核心目标。一旦掌握，你就能将其应用于各种问题。

关键收获

记住：采用不同策略可以显著改善时间或空间复杂度。排序使时间复杂度大幅下降。

合理使用数据结构也能提升效率。尝试用对象、数组、Set、栈或队列来存储数据，看看是否能打开新的解决思路。