[力扣_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,所以只有出现的时候才会匹配上!也就是说,程序是先判断此字符是否出现过,才来决定是否更新起始点。如果没出现,则长度增加,出现过,则计算长度并更新起始点。开始新一轮的计算