算法入门C——3. 无重复字符的最长子串

LeetCode刷题——算法学习计划（入门部分）

• 题目描述
• 思路介绍
• 我的第一次正确提交
• 网友版本

个人思路：
定义两个指针p和q，p指向无重复子串的第一个字符，q用来判断子串是否存在重复字符。

一开始两个指针都指向字符串开头，如果*q在以p开始，长度为count的字符数组中无重复字符，则将count加1，同时q向右移动；如果检测到重复的字符，则将p右移1位，同时将q指向p，判断此时count是否大于当前最长子串数max，如果大于，将count赋值给max，同时将count清零，准备测量下一个无重复子串。

当p或q指向字符串末尾时，循环结束，如果首先是q到达字符串末尾，说明最后一个子串没有重复，但此时在循环里还没有判断最后一个不重复子串长度是否大于当前最大无重复子串最大长度。所以需要在循环结束后还需要比较一次count和max的值。

依据个人思路编写的代码：

int is_Repeat(char *s, int len, char target)
{
    int i = 0;
    for(i = 0; i < len; i++)
    {
        if(s[i] == target)
        return 1;
    }
    return 0;
}

int lengthOfLongestSubstring(char * s)
{
    char *p = s, *q = s;
    int max = 0, count = 0;
    while(*p && *q)
    {
        if(is_Repeat(p, count, *q) == 0) //不重复
        {
            count++;
            q++;
        }
        else
        {
            p++;       //从下一个字符开始判断
            q = p;     
            if(count > max)
                max = count;
            count = 0;
        }
    }
    if(count > max)  //最后一个子串长度还没比较
        max = count;
    return max;
}

效率比较低。

官方介绍的方法为滑动窗口，但没有给出C语言版本代码，因为C语言不带哈希集合。
所以我引用了一个力扣题解（评论）中的很棒的方案
原文链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hashhua-dong-chuang-kou-c-by-sirius-dotc-3fup/

理解上，我主要卡在if(index[s[i]]>left){ left = index[s[i]];}，首先要明确一点——left是窗口左边界的前一个位置，而不是左边界，例如，窗口有一个字符a，那么index[a]的值就是它在窗口中的位置（位置值一定比left大，即index[a]>left，假如不在窗口中，那么index[a]为-1），如果此时在字符串中再次检测到另一个a，要想保证滑动窗口的字符不重复，那么这时需要将窗口的左边界移动到之前a的位置，即left=index[a]。

int lengthOfLongestSubstring(char * s)
{
    int i;  
    int index[128];
    for(i=0;i<128;i++){
        index[i]=-1;
    }
    int left =-1;                        //left 是窗口左边界的前一个位置
    int len =strlen(s);
    if (len ==1) return 1;
    int count =0; 
    for(i=0;ileft){            //若 index[s[i]] > left 成立，说明之前出现过的字符在窗口内
            left = index[s[i]];
        }
        if(count 
该程序的耗时：
 
 
 
下面是我的一个失败的提交记录
 
 
 
考虑不周，当检测的子串出现重复字符时，需要将p向指向下一字符，而不是向后移动count（当前位置的上一个最大不重复子串的长度）。
 
 
 


int is_Repeat(char *s, int len, char target)
{
    int i = 0;
    for(i = 0; i < len; i++)
    {
        if(s[i] == target)
        return 1;
    }
    return 0;
}

int lengthOfLongestSubstring(char * s)
{
    char *p = s, *q = s;
    int max = 0, count = 0;
    while(*q)
    {
        if(is_Repeat(p, count, *q) == 0) //不重复
        {
            count++;
            q++;
        }
        else
        {
            p += count;
            if(count > max)
                max = count;
            count = 0;
        }
    }
    if(count > max)  //最后一个子串长度还没比较
        max = count;
    return max;
}