題目
給定一個(gè)字符串尘盼，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"兼吓，所以其長(zhǎng)度為 3臂港。
解題思路
1 .滑動(dòng)窗口
#python
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
ans = 0
s_t = ""
for i in s:
if i in s_t:
s_t=s_t.split(i)[-1]
s_t += i
ans = max(ans,len(s_t))
return ans
思想簡(jiǎn)單，效率一般
2 桶排序视搏？
//c
int lengthOfLongestSubstring(char * s){
int start = 0, end = 0, maxlen = 0;
char map[512] = {0};
map[(int)*(s+start)] = 1;
while( *(s+end) != 0 )
{
maxlen = maxlen>(end-start+1)?maxlen:(end-start+1);
++end;
while( 0 != map[ (int)*(s+end) ] )//將要加入的新元素與map內(nèi)元素沖突审孽，然后循環(huán)自增start=end
{
map[ (int)*(s+start) ] = 0;
++start;
}
map[(int)*(s+end)] = 1;
}
return maxlen;
}
評(píng)論中看到的，時(shí)間復(fù)雜度超過100%的人浑娜。
