LeetCode-3.无重复字符的最长子串 利用一个整形数组+ASCII码实现滑动窗口

先看题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 : 输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

分析如下
方案一：从头到尾用两层循环比对字符，时间复杂度O(n²)，不推荐
方案二：我想到了利用一个整形数组，下标对应字符的ASCII码，然后值存字符最新出现的数组位置。 这里我用len代表当前累计长度，i为字符在字符数组中的位置，tag为当前子串的起始位置。这样做只需对该字符数组进行一次遍历，时间复杂度为O(n)。

c语言解法如下

int lengthOfLongestSubstring(char * s){
    //常用字符ASCII码范围是0~128，开150的数组绰绰有余
    int tem[150]={0};
    int len = 0,i=1,result=0,tag=0;
    while(*s != '\0'){
        int a = s[0];
        if(tem[a]==NULL || tem[a]<tag){
            tem[a] = i; //标记该字符存在的最新位置
            len++;
        }else{
            result=len>result?len:result;
            tag=tem[a];
            len=i-tag-1;
            tem[a]=NULL;
            continue;
        }
        s++;
        i++;
    }
    return len>result?len:result;
}

最后提交结果如下，可以看到算法还可以继续进行优化：
执行用时： 4 ms, 在所有 C 提交中击败了84.91%的用户 内存消耗： 5.5 MB, 在所有 C 提交中击败了100.00%的用户

文章永久链接：https://tech.souyunku.com/27328