Longest Substring Without Repeating Characters 字符串中最長的無重復子串長度

Longest Substring Without Repeating Characters 字符串中最長的無重復子串長度

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

題目的意思是求字符串中最長的無重復子串長度，如上面的 abcabcbb 最長無重復子串為abc 長度為3

直接暴力法：代碼如下

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
       int i,j,temp,result=1;
        
        for(i=0;i

暴力法雖然簡單，但時間過不了，下面用一個復雜度為n的算法




思路：
用一個256位數組asc[]（字符共有256個，包括128個擴展字符），字符串中每一個字符的ASCII值對應該字符在數組中的位置
如字符a
  在   asc[a]中的下標為97
初始化數組asc，令每一個元素為-1。定義start,start表示每次無重復字符串的其實點，初始值為0.從i=0開始遍歷字符串，如果數組asc中沒有出現該字符(asc[ch]==-1)，那麼令asc[ch]==i,記錄下來該字符在字符串中的位置，接著遍歷，如果遇到asc[ch]！=-1表示該字符已經出現了，需要將start到j的asc數組中的元素抹掉。然後重置start,令start=max(asc[i]+1,start);然後將
最後結果為   result=max(result,i-start);
代碼如下：
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
       
        
        int result=0;
        int a[128];
        int i,j,t,start=0;
        
        for(i=0;i<128;i++)
            a[i]=-1;
            
        for(i=0;i