一、題目

Longest Substring Without Repeating Characters.png

二、解題

1）題意

• 題目的意思還是比較好理解的，輸入一個(gè)字符串，找出沒(méi)有重復(fù)字符的最長(zhǎng)子串，返回其長(zhǎng)度。
  例如abcabcbb，abc為最長(zhǎng)的無(wú)重復(fù)字符的子串，如果是abca或者bcab則出現(xiàn)了重復(fù)了。

2）關(guān)鍵點(diǎn)

• 子串沒(méi)有重復(fù)，即子串里面沒(méi)有重復(fù)的字符。
• 子串是需要連續(xù)的。

三、思考：

• 使用遍歷的方式，存儲(chǔ)最長(zhǎng)的字符串長(zhǎng)度在maxlength
• 使用兩個(gè)下標(biāo)（i、j），i從0開(kāi)始，j從i+1開(kāi)始，在沒(méi)有重復(fù)的情況下，j每次增加1（步長(zhǎng)為1），取出當(dāng)前的標(biāo)記下標(biāo)的子串tempStr（從i到j(luò)、包括j），計(jì)算tempStr長(zhǎng)度并記錄到templength，與maxlength比較，大則賦值。
• （關(guān)鍵點(diǎn)）當(dāng)遇到重復(fù)的時(shí)候：找到重復(fù)的位置，并把i移動(dòng)到此處，j不變，然后循環(huán)繼續(xù)。在python代碼中，使用find是找到的tempStr的下標(biāo)，要換成源字符串的下標(biāo)表則需要加上原來(lái)的i的位置。

四、嘗試與結(jié)果

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        if (len(s) <= 1):
            return len(s)

        i = 0
        j = 1
        tempStr = s[0:1]
        templength = 1
        maxlength = 1

        while (True):
            c = s[j]
            if (c in tempStr):
                t = tempStr.find(c) + 1
                i = i + t #新的i的坐標(biāo)

             #當(dāng)下標(biāo)為j時(shí)，s[i:j]這個(gè)字串是不包括j的，所以要把j+1（切片不會(huì)越界）
            tempStr = s[i:j+1] 
            templength = len(tempStr)

            if (templength > maxlength):
                maxlength = templength
            j = j + 1

            if (j >= len(s)):
                break

        return maxlength

結(jié)果：AC