[力扣_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)

img

这儿需要注意一个地方:

img

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

动画地址

本文链接:

https://nullcode.fun/48.html
1 + 3 =
快来做第一个评论的人吧~