JavaScript 确定一个字符串的所有字符均不同

上次去Google Girls送了我一本面试金典，前天无聊就看了起来，看到的部分目前还是比较基础也有些意思的，在我看到第一堆算法题的时候我说了一句，这个题看着有点简单啊……然后秒被打脸，可以说，所有的题都是想简单就简单，想难就难，主要看你考虑了多少。

今天就拿其中一道题来说说上面的观点。

实现一个算法，确定一个字符串的所有字符是否不同，假设不允许使用额外的数据结构，又该如何处理。

看完题目，能想到的基本有四种方法，大致总结一下：

第一种叫做直接查找，就是两层循环挨个找，找到相同就跳出。这里毫无疑问时间复杂度O(n^2)，不太靠谱啊。（JS中直接用indexOf）

第二种，先排完序，基本上语言们自带的sort都是快排，O(log(n))，排完再来个O(n)的循环前一个比后一个就能比出来了。

第三种，哈希表，简单粗暴。（JS中用Object或者Map）

第四种，数组统计。（类似于桶）

上面两种如果用C语言实现都是数组去构建的话只是空间不同，时间都是O(n)就行。

之后我们来考虑一下，既然都用JS了，要不试试Map吧——本来我也是这么想的，但是鉴于这是字符串中的字符，不需要区分1和'1'，似乎没有这个必要。

想完一波，是不是太简单了？不对，当时在没有用到额外数据结构的时候我想到的是第四种，但是很快就想到了问题，一般而言我们统计英文当然可以，但是现在除了英文，可能是别的文字吧，那样范围就从ASCII扩展到了UNICODE，那还玩个什么，但是等等，这是歪果仁写的书，会不会限制就是英文。

苦思不得其解，翻到了答案……发现他果然考虑了这个问题……然后做了个ASCII的范围假设。

const uniqueOrNot2 = function(str) {
  const length = str.length;
  const table = new Array(256);
  let char = 0;

  if (length > 256) {
    return false;
  }

  table.fill(false);

  for (let i = 0; i < length; i++) {
    char = str.charCodeAt(i);
    if (!table[char]) {
      table[char] = true;
    } else {
      return false;
    }
  }

  return true;
}

这里其实又有另一个优化，这个我最初没有考虑到（最初我还在纠结限制范围），那就是如果你知道编码方式，实际上是可以限制字符串长度的最大值，超过长度根本不需要比较。

之后还有一个前方高能版，就是用位运算，其实和数组是一样的，又节省的空间，而且位运算通常更快：

const uniqueOrNot3 = function(str) {
  let checker = 0;
  let start = '0'.charCodeAt(0);
  let diff = 0;
  const length = str.length;

  for (let i = 0; i < length; i++) {
    diff = str.charCodeAt(i) - start;

    if ((checker & (1 << diff)) > 0) {
      return false;
    }

    checker = checker | diff;
  }

  return true;
}

然后我默默收回了说他们简单的话……

详情：https://github.com/csvwolf/Sky_JavaScript_Learning/blob/master/Cracking-the-Coding-Interview/char-unique-in-string.js