0003无重复的最长子串_Leon

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

注意：字符和字符串的遍历关系：直接索引是否在就行
注意：用切片删除最左边的重复字符即可，那样剩下的字符串仍然是不重复的子字符串了
思路：
双重复循环操作：使用字典集合cur_Str 、 res_Str实现遍历循环中的组合记忆操作，第一轮循环中，将两个集合均将当前首个元素的值添加进set中，然后以此 i 为基准，进行下一次的迭代，把cur_Str当成验证工具，进行set.add(element)操作，之后再比较len（cur）与len（res），若两者长度相等，则说明遇到重复元素，否则就说明当前元素为独立不重复的，此时就可以放心的把当前元素s[j]加入res集合中了；内层循环结束后，使用max_Len记忆最大不重复字串的长度，进行下一轮循环即可。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cur_Str = set([])
        res_Str = set([])
        length = len(s)
        max_Len = 0
        for i in range(length):
            cur_Str = set(s[i])#初始化当前字符集合，将首位添入
            res_Str = set(s[i])#同理，初始化结果集合，至少为 1
            j = i + 1
      #      while(j < length):
            for j in range(i+1,length): #while 和 for in range(start, bounding_value)两种写法均可
                cur_Str.add(s[j])
                if(len(cur_Str) > len(res_Str)):#判断是否重复
                    res_Str.add(s[j])#不重复，结果集合添加元素，继续向后走
                else:#如果长度相等，则说明一定出现了重复元素，直接break，进行下一轮次的迭代
                    break
       #         j += 1
            max_Len = max_Len if max_Len > len(res_Str) else len(res_Str)#下一轮之前，首先更新max_Len的值
        return max_Len

用cur和res记录最长字串和当前字串长度，然后字符串的第一个字符开始遍历，记录当前子串，然后判断如果当前字符是否在cur中，如果在的话就先比较重复字符之前的res字串和cur字串的长度，取最大的为res字串；
然后和之前一样的操作，先将当前字符合并进cur字串中，再把cur子字符串中重复字符给删除掉，用切片即可实现；
继续更新迭代即可；
这里有一个边界情况，就是字符串全部相等时，res子串不会得到更新，因此需要再循环语句之后，进行兜底。
代码还可以继续优化。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        current_Str = ''
        result_Str = ''
        for index in s:
            if index not in current_Str:
                current_Str += index
            else:
                if len(result_Str) < len(current_Str):
                    result_Str = current_Str
                current_Str += index
                current_Str = current_Str[current_Str.index(index)+1:]
        if len(result_Str) < len(current_Str):
            result_Str = current_Str
        return len(result_Str)

优化V2:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cur_Str = ''
        max_Len = 0
        for index in s:
            if(index not in cur_Str):
                cur_Str += index
                max_Len = max_Len if max_Len > len(cur_Str) else len(cur_Str)
            else:
                cur_Str += index
                cur_Str = cur_Str[cur_Str.index(index) + 1 :]
        return max_Len

最后编辑于：2019.07.24 11:40:44