leetcode-3 Longest Substring Without Repeating Characters

題意: 給定一串字串,求出不含有重覆字符的最常連續子字串的長度


解題思路: 利用尺取法,逐次推進,當遇到重覆字符時,重置累積的長度,須考慮兩種狀況,第一種狀況,前一個重覆的字符位置,ex. "bbcabcdef",當遇到第二個c時,須將長度從舊的c的下一個起算;第二種情況,若有其他組重複字符,其前一個重覆元素在目前指到元素的前一個重覆元素之後的話,則須從這種情況開始計算,ex. "cabbcdef", 當遇到第二個時,並不是從前一個c開始計算,而是從前一組重覆字符,也就是b起算,complexity為O(n),其中n為字串長度


c++程式碼如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int eng[600][2];
        memset(eng,0,sizeof(eng));
        int len=s.length();
        int count=0;
        int ans=0;
        int temp=-1;
        for(int i=0;i<len;i++)
        {
            if(eng[s[i]][0])
            {
                
                if(ans<count)
                    ans=count;
                if(eng[s[i]][1]>temp)
                    temp=eng[s[i]][1];
                if(temp>eng[s[i]][1])
                    count=i-temp;
                else
                    count=i-eng[s[i]][1];
                eng[s[i]][1]=i;
                
                
            }
            else
            {
                eng[s[i]][0]=1;
                eng[s[i]][1]=i;
                count++;
            }
            //cout<<count<<endl;
        }
        if(count>ans)
            ans=count;
        return ans;
    }
};