春招打卡第03篇——无重复字符的最长子串

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

给定一个字符串 s ，找出其中不含有重复字符的 最长子串 的长度。查看题目来源

二、思路分析

我的思考过程

首先，子串就是从字符串中截取出来的一个片段，是连续的。这样一来，要解决这个题目的逻辑也挺简单的

先解决问题：穷举遍历，从第一个字符开始遍历，截取出没有重复字符的子串，然后将这个子串的长度存起来；从第二个字符开始遍历，截取，与前面保存的子串长度比较，如果新的子串更长，那么就替换掉。总体的思路有点类似于冒泡排序的思路。

思路是这个思路，但是用代码啊实现时需要更加详细的步骤才容易敲出代码：（因为刚开始敲不出）

首先需要一个数组 charTemp ，用来存放每次截取的子串，判断是否有重复字符，该数组的最大长度是 26+26+10+1+32+1 = 96（字母+数字+空格+符号+\0，符号我只计算了键盘能输入的符号）。还需要一个变量 head，用来指定起始位置。还需要一个变量 result ，用来保存当前得到的最长子串，该变量同时也是最终的返回结果。还需要一个临时变量 length ，用于计算子串长度，每次改变起始位置时，需要将其置零。

首先从第一个字符开始，将该字符添加 charTemp 中，判断一下是否重复，不重复则 length++ 然后取出第二个字符（第二个字符在完整字符串中的位置可以使用 result 和 length 计算出来，所以就不需要一个新的变量了）；

如果重复，将 length 与 最大长度 result 比较，看看是否覆盖 result ，然后开始下一轮（令 head++），重复上面的操作，直到 head 到达结尾（在这里我想到我们不需要等到等到 head 到达结尾，只需要 head 和结尾的距离小于当前最大值 result 就行，不过应该没有计算出字符串长度，故先放下该想法）

理解优秀代码的思路

通过一步一步调试优秀代码，我认为思路应该是这样的：

我们需要 求的是最长的不重复的子串长度，要提高效率重点就是如何减少遍历的子串数量，前面我的方法是遍历出所有情况，这样的效率是非常低的。对此进行改进就是想象一下有两个指针 start 和 end，start 肯定不能在 end 后面，并且我们要确保 start 和 end 之间的字符一定是没有不重复的！即 [start - end] 所在子串始终为不重复子串。那么我们要如何实现呢？

使用一个案例来理解，假设字符串为 abcdec

首先，两个指针都从起点开始，然后判断一下 end 所在字符 a 是否存在，明显不存在，故存起来。此时不重复子串为 [0-0] 然后让 end++，重复上面的操作。

当 end 为 5 时所在字符为 c 时，判断得到已经存在 c 字符，此时 [0-5] 子串不满足无重复字符 的条件，故需要修改 start 的值为 3，确保此时的子串 [3-5] 为不重复子串。同样需要让 end++

重复上面的操作，直到 end 到达结尾。在此过程中，我们能够保证所有的 不重复子串 都被遍历到了，那么只需要将其中最长的子串长度保存起来，就解决了答案。

上面就是我对优秀代码的理解，但要我证明上面的过程能够遍历到 最长的不重复子串 ，我说不清楚，但是能感觉到这样子是对的：end 尽了最大的能力要远离 start ，而且 start 也尽了最大的力气“待着不动”，但当 end 遇到了一个重复字符时，start 必须得移动，因为他们要确保 [start - end] 之前是不重复的子串。

根据上面的思路，实现时需要思考的点有这么几个：

• 如何存字符？
• 怎样判断已存在该字符？
• start 如何定位到出现重复字符的位置？

1. 采用简单粗暴的方式，直接存起来

   最终结果是原字符串有多长，临时存储空间就有多大。
   这种情况下，是在 [start - end] 范围内判断是否存在该字符。
   定位方式就是让 start++ 直到 start 所在的值和当前 end 所在的值一样

2. 将 char 看成 int

   因为字符本身所代表的的 ASCII码 并不大，所以我们可以将 char 本身看成 int 这样一来，我们在存储时，char 本身就是下标，我们在判断时，也不再需要通过遍历去判断是否存在，只需要直接使用 char 作为下标就可以判断是否存在。

   此时我们需要一点，就是要注意即时清理已经不在不重复子串中的字符，即在对 start 进行定位时，需要注意下面这行代码

   while (*(s+start) != *(s+end)) {
       store[ *(s+start) ] = 0; // 清理
       start++;
   } 
   复制代码

遇到的问题

• ==42==ERROR: AddressSanitizer: heap-buffer-overflow on address

这个问题是老朋友了 ಥ_ಥ ，地址溢出错误，原因我没有要添加进 charTemp 的值进行判断

int add (char *charTemp, char val) {
    ...
    if (*charTemp == val) // 错误代码，没有对 val 进行判断
    if (*charTemp == val || val == 0) // 正确代码
    ...
}
复制代码

还需要注意的就是要给 charTemp 多少内存大小，计算时需要注意要有一个位置用来作为结尾标识 \0

• 使用优化代码后提交，无法通过 " " 单个空格字符串 和 "" 空字符串的情况

简单粗暴的解决：

if (*s == 0)
    return 0;
if (*(s+1) == 0) 
    return 1;
复制代码

• store to address 0x62c001ecf730 with insufficient space for an object of type ‘char’

翻译：空间不足。原因是我采用的存储方式很粗暴，原字符有多长，我就需要创建多长的存储空间。粗暴的解决方式就是复制无法通过的字符串，查看其长度，然后修改 malloc 中的值

...
char* store = malloc(sizeof(char)*31656); // 测试用例中最长的字符串长 31655
...
复制代码

三、AC 代码

感觉效率很低，因为只超过了不到 10% 的用户（时间和内存）

int add (char *charTemp, char val) {
    while (*charTemp != 0) {
        if (*charTemp == val || val == 0)
            return 0;
        charTemp++;
    }
    *charTemp = val;
    *(charTemp+1) = 0;
    return 1;
}

int lengthOfLongestSubstring(char * s){
    char* charTemp;
    int head = 0;
    int result = 0;
    int length;
    while (*(s+head) != 0) {
        length = 0;
        charTemp = malloc(sizeof(char)*96);
        *charTemp = 0;
        while (add(charTemp, *(s+head+length))) {
            length++;
        }
        if (length > result)
            result = length;
        head++;
    }
    return result;
}
复制代码

参考优秀代码后，对算法进行改进（存储方式采用粗暴方式，故内存方面效果不好，但是耗时方面，能够实现 0ms）

int isThere (char *head, char val) {
    while (*head != 0) {
        if (*head == val || val == 0)
            return 1;
        head++;
    }
    return 0;
}

int lengthOfLongestSubstring(char * s){
    if (*s == 0)
        return 0;
    if (*(s+1) == 0) 
        return 1;
    char* store = malloc(sizeof(char)*31656);
    int start = 0;
    int end = 0;
    int maxLength = 0;
    while (*(s+end) != 0) {
        *(store+end) = *(s+end); // 存
        end++;
        *(store+end) = 0;
        if (isThere(store+start, *(s+end))) { // 判断
            while (*(s+start) != *(s+end)) // 定位
                start++;
            start++;
        }
        if (maxLength < end-start+1) 
            maxLength = end-start+1;
    }
    return maxLength;
}
复制代码

对内存进行优化

int lengthOfLongestSubstring(char * s){
    char store[256] = {0};
    int start = 0;
    int end = 0;
    int maxLength = 0;
    while (*(s+end) != 0) {
        if (store[ *(s+end) ] == 0) { // 判断
            store[ *(s+end) ] = 1; // 存
        } else {
            while (*(s+start) != *(s+end)) { // 定位
                store[ *(s+start) ] = 0; // 清理
                start++;
            } 
            start++;
        }
        end++;
        if (maxLength < end-start) 
            maxLength = end-start;
    }
    return maxLength;
}
复制代码

四、总结

在第一版的代码中，有一个地方有点不理解，就是我如果专门去 free(chatTemp)，占用的内存反而会多一些？对此我能做出的理解是： 当创建出的一块空间 malloc() 丢失了它的指针时(没有指针指向它)，它就会被自动销毁，所以如果我专门去 free 系统反而需要耗费一些资源去执行 free 函数。

看了优秀代码后，并尝试读懂思路和自己实现时才发现自己真的好菜。