数组_leetcode3

#coding=utf-8

# 解题思路:
# 滑动窗口问题: 字典的使用是关键 map hash 表的使用  20190302 找工作期间

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        if s == "":
            return 0

        record = {}

        start = 0
        end = 0
        ans  = 1

        res = 1


        record[s[start]] = start

        while end < len(s):

            if end+1 < len(s):

                if s[end+1] not in record:
                    end += 1
                    ans += 1
                    record[s[end]]=end
                else:
                    res = max(ans, res)

                    newstart = record[s[end+1]]+1

                    for i in range(start,newstart):
                        record.pop(s[i])
                    start = newstart
                    end += 1
                    record[s[end]] = end
                    ans = end - start + 1

            if end == len(s)-1:
                ans = max(ans,res)
        return res

class Solution2(object):
    def lengthOfLongestSubstring(self, s):

        temp = res = ""
        for item in s:  # 对于字符串s中的每个字符
            if item not in temp:  # 如果这个字符不在temp当中
                temp += item
                if len(temp) > len(res):
                    res = temp
            else:
                i = temp.index(item)  # 找到索引
                if i == len(temp) - 1:
                    temp = item  # 如果到达末尾
                else:
                    temp = temp[i + 1:] + item  # 没达到末尾
                if len(temp) > len(res):
                    res = temp
        return len(res)



st = "abcabcbb"
# st = "pwwkew"
# st = "au"

s = Solution()

print s.lengthOfLongestSubstring(st)