Leetcode——劍指offer3. 無重複字元的最長子串

方法一二判斷相等的方法還是空間換時間，維護一個長度128的flag的bool數組（涵蓋ascll表），通路一次數組元素置true，二次通路則說明有重複元素。

方法一：

暴力

時間複雜度O(n^3)

最長的測試用例逾時

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int length=s.size();
        bool re=true;
        for(int i=length;i>=2;i--)
        {
            for(int j=0;j<=length-i;j++)
            {
                re=true;
                bool flag[26]={false};
                int temp;
                for(int k=j;k<j+i;k++)
                {
                    temp=int(s[k])-97;
                    if(flag[temp]==true)
                    {
                        re=false;
                        break;
                    }
                    else
                    {
                        flag[temp]=true;
                    }
                }
                if(re)
                {
                    return i;
                }
            }
        }
        return 1;
    }
};

           

方法二：

掃描，時間複雜度O(n^2)，可以過全部用例，但是還是比較慢，不滿意。

大體思路：從頭開始掃描，遇到重複字元就将初始的位置+1，後來想優化一下，類似kmp的思路，就是維護一個二維數組，【x】【0】記錄是否通路，【x】【1】記錄位置，以後x元素重複了可以直接從【x】【1】開始再找，相當于多向前走了幾步，而不是一步一步走。按理來說，這樣寫時間複雜度是O(n),但是可能通路二維數組比一維數組慢，不但沒有變快反而變慢了。都把代碼貼出來。

原始版

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int length=s.size();
        if(length==0)
        {
            return 0;
        }
        int re=1;
        int temp;
        int dis=0;
        for(int i=0;i<length;i=i+1)
        {
            bool flag[128]={false};
            dis=0;
            for(int j=i;j<length;j++)
            {
                temp=int(s[j]);
                if(flag[temp]==true)
                {
                    break;
                }
                else
                {
                    flag[temp]=true;
                }
                dis++;
            }
            if(dis>re)
            {
                re=dis;
            }
        }
        return re;
    }
};
           

“優化版”

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int length=s.size();
        if(length==0)
        {
            return 0;
        }
        int re=1;
        int temp;
        int dis=0;
        int a=0;
        int ahead=0;
//        string str="pwwkew";
        for(int i=0;i<length;i=ahead)
        {
            int flag[128][2]={0};
            ahead=i+1;
            dis=0;
            for(int j=i;j<length;j++)
            {
                temp=int(s[j]);
                if(flag[temp][0]==1)
                {
                    ahead=flag[temp][1]+1;
                    break;
                }
                else
                {
                    flag[temp][0]=1;
                    flag[temp][1]=j;
                }
                dis++;
            }
            if(dis>re)
            {
                re=dis;
            }
        }
        return re;
    }
};

           

方法三：

滑動視窗

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int ssize=s.size();
        if(ssize==0)
            return 0;
        int start(0),re(0),length(0);
        char temp;
        for(int i=0;i<ssize;i++)
        {
            temp=s[i];
            length=i-start;
            for(int j=start;j<i;j++)
            {
                if(s[j]==temp)
                {
                    start=j+1;
                    length=i-start;
                }
            }
            length++;
            if(length>re)
            {
                re=length;
            }
        }
        return re;
    }
};
           

方法四

哈希存儲出現重複的字元最後一次出現的位置。和我方法二中企圖用二維數組實作一個思路，但是hash快多了。複雜度 O(n)

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        //s[start,end) 前面包含 後面不包含
        int start(0), end(0), length(0), result(0);
        int sSize = int(s.size());
        unordered_map<char, int> hash;
        while (end < sSize)
        {
            char tmpChar = s[end];
            //僅當s[start,end) 中存在s[end]時更新start
            if (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start)
            {
                start = hash[tmpChar] + 1;
                length = end - start;
            }
            hash[tmpChar] = end;

            end++;
            length++;
            result = max(result, length);
        }
        return result;
    }
};