每日一道算法题 无重复字符的最长子串
题目
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 字典记录字符的位置
record={}
l=-1
ans=0
for r in range(len(s)):
if s[r] in record:
l=max(record[s[r]],l)
# l=record[s[r]]
record[s[r]]=r
ans=max(ans,r-l)
return ans
为什么l=max(record[s[j]],l)?
“abba”,当遍历到第二个“a”的时候,左指针又跳回到左边的a上去了 所以更新左指针这一行l = max(dic[s[r]], l)中的max神来一笔,保证了左指针无论如何不会往左跳 .
C++
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
unordered_map<char,int> record;
int l=-1,ans=0,len=s.size();
for(int r=0;r<len;r++)
{
if(record.find(s[r])!=record.end()) l=max(l,record.find(s[r])->second);
record[s[r]]=r;
ans=max(ans,r-l);
}
return ans;
}
};
C语言
int lengthOfLongestSubstring(char* s)
{
int ans=0,l=0;
bool record[128]={};
int len=strlen(s);
for(int r=0;r<len;r++)
{
char c=s[r];
while(record[c]) record[s[l++]]=false;
record[c]=true;
int n=r-l+1;
ans=n>ans?n:ans;
}
return ans;
}
原文地址:https://blog.csdn.net/weixin_65816128/article/details/140598688
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!