[力扣_3] 无重复字符的最长子串

题目入口：点击进入

相关算法：

• 滑动窗口——时间复杂度：O(n)，空间复杂度O(m)
• 哈希映射实现滑动窗口

这道题主要用到思路是：滑动窗口

什么是滑动窗口？

• 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

我们只要把队列的左边的元素移出就行了，直到满足题目要求！这儿的移出来是抽象的

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

代码如下：

int lengthOfLongestSubstring(char * s){
    int HashSet[128];
    int sleng=strlen(s);
    if(sleng<2)
    {
        return sleng;
    }
    int start=0;
    int maxlen=0;
    int curlen=0;
    memset(HashSet,-1,sizeof(HashSet));

    for(int i=0;i<sleng;i++)
    {
       if(HashSet[s[i]]>=start)
       {
        start=HashSet[s[i]]+1;//
        curlen=i-start;
       }
        HashSet[s[i]]=i;
        curlen++;
       if(curlen>maxlen)
       {
           maxlen=curlen;
       }
     }
    
     return maxlen;
}

LeetCode里边的string严格来说并不算string，它是一个char Array。字符用ASCII存放。

我们可以用数组(桶代替hashmap)

这儿需要注意一个地方：

这判断语句在前面，而i是不断递增的，如果在桶中未出现过此字符，那么这时桶的值是-1，所以只有出现的时候才会匹配上！也就是说，程序是先判断此字符是否出现过，才来决定是否更新起始点。如果没出现，则长度增加，出现过，则计算长度并更新起始点。开始新一轮的计算

动画地址

本文链接：