---
title: LeetCode - Longest Substring Without Repeating Characters
date: 2018-11-19T16:34:00+08:00
tags:
  - 技术

---

最近启动了刷 LeetCode 的进程，Accepted 了几道题，但两天不到就忘了，即使是留了注释，想想写写笔记还是蛮有必要的，但我不希望不经思考整理就贴一堆代码，把博客搞的乱糟糟的，像 XSDN、XX园、X书 一样，所以也只是想把一些印象深刻的部分，留个笔记。

过去的我过于年少轻狂，把某些高级语言当成了全部，并未好好去用 C/C++ 写过点什么。忽视了那些底层的基础的后果便是，现在在写一些很简单的东西，在需要保证代码质量的时候，要纠结许久去思考某一段代码需要消耗比较大的代价才能下决定。用 C 语言写代码有个好，通过它可以让你弄清楚，计算机底层可以给你什么基本能力，什么能力是需要通过这些基本的东西通过封装的方式实现的，也相当于顺便强化计算机基础了，所以我也打算就用 C 来刷这一套算法题。

---

题目：

> 3.Longest Substring Without Repeating Characters
> 
> 
> Examples:
> 
> Given `"abcabcbb"`, the answer is `"abc"`, which the length is 3.
> 
> Given `"bbbbb"`, the answer is `"b"`, with the length of 1.
> 
> Given `"pwwkew"`, the answer is `"wke"`, with the length of 3. Notethat the answer must be a substring, "pwke" is a subsequence and not asubstring.
> 

程序需要统计输入字符串的最长无重复子串的长度。最初想到的是，从第一个字符开始，遍历这个字符的字符，直到出现重复的字符，统计此时的字符串长度，然后从第二个字符开始，重复这个过程，取最大的一个，直到最后一个字符为止，其中因为边界的问题的处理，折腾了许久，不过还是实现了下面的第一版的代码：

```c
int lengthOfLongestSubstring(char* s) {
    int p = 0;
    char c;
    int maxLen = 0, tempLen = 0;
    while (s[p] != '\0') {
        int q = p + 1;
        while ((c = s[q]) != '\0') {
            int hasRepeat = false;
            for (int i = p; i < q; i++) {
                if (s[i] == c) {
                    hasRepeat = true;
                    break;
                }
            }
            if (hasRepeat) {
                break;
            }
            q++;
        }
        if ((tempLen = q - p) > maxLen) {
            maxLen = tempLen;
        }
        p++;
    }
    return maxLen;
}
```

这段代码在 leetcode-cn.com OJ 上的运行时间是 180ms，只战胜了 29% 的 C 语言提交，显然这个 O(n^3) 的算法并没有什么竞争力。

这段算法有一个地方比较浪费 CPU 的是，在一个字符失败以后，又重叠判断了一部分相同的元素，看题解提示说用一种 “Sliding Window” 的方法（名字听起来好像 TCP 协议的发送窗口~），通过这种方法，我们只需要把其中不重复的部分保持起来，出现重复的话，就把开头的字符排除掉，这样，这部分字符仍然保持不重复，但是往前移动了一位，就不需要再回头比较元素是否重复了。

题解是用 Java 来写的，用了哈希表去保存字符的状态，C语言上哪找哈希表啊，不过不急，先改改看看什么情况，就有了下面的代码：

```c
int lengthOfLongestSubstring(char* s) {
    if (s[0] == '\0') return 0;
    int p = 0, q = 1;
    char c;
    int maxLen = 1, tempLen = 0;
    while ((c = s[q]) != '\0') {
        bool hasRepeat = false;
        for (int i = p; i < q; i++) {
            if (s[i] == c) {
                hasRepeat = true;
                break;
            }
        }
        if (hasRepeat) {
            p++;
        } else {
            q++;
        }
        if ((tempLen = q - p) > maxLen) {
            maxLen = tempLen;
        }
    }
    return maxLen;
}
```

其中补充了空白字符的情况，复杂度降到了 O(n^2)，OJ 显示花了 32ms，战胜了 49% 的提交，想想，还是有进步空间啊。

剩下的问题就是这个判断重复的循环了，像题解的哈希表一样，把一个个的遍历，换成一键查询得到结果，可以变得更快！但是，C语言并没有原生实现哈希表数据结构，要实现一个，显然，哈希函数跑起来的开销估计可能比这个循环还大吧。

仔细分析需要做一对一映射的数据。每次循环需要查询的只是一个 char ，大小是一个字节，本身只有 256 种情况，而可见字符都遵循 ASCII 编码，也就是说，本题目给的输入中，最多只是前 128 种情况。

面对这样的需求，在C语言里面，开个 128 长度的数组，显然就能覆盖所有的情况了，其中的冗余，在内存不要钱的今天，显然也是可以接受的。

稍微改改，把这一个查找代码

```c
bool hasRepeat = false;
for (int i = p; i < q; i++) {
    if (s[i] == c) {
        hasRepeat = true;
        break;
    }
}
```

换成利用 C 数组实现的 char->boolean 的字典：

```c
int lengthOfLongestSubstring(char* s) {
    // only zero
    if (s[0] == '\0') return 0;
    int p = 0, q = 1;
    char c;
    int table[128] = {0};
    table[s[p]] = 1;
    int maxLen = 1, tempLen = 0;
    while ((c = s[q]) != '\0') {
        if (table[c]) {
            table[s[p++]] = 0;
        } else {
            table[s[q++]] = 1;
        }
        // calc
        if ((tempLen = q - p) > maxLen) {
            maxLen = tempLen;
        }
    }
    return maxLen;
}
```

时间复杂度降到 O(2n) = O(n)，运行时间降到了 12ms，~~愉快地击败了 100% 的 C 语言提交~~