About

今天是刷LeetCode的第五天，不敢称之为挑战了，因为发现自己还是太弱小，很久不写代码脑子都锈了，每次做出的题解在性能上都和大神有很大的差距，但是为了提高我的代码质量，我必须坚持下去！

无重复字符的最长子串

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

输入: "pwwkew"
输出: 3

解题思路

1. 创建一个空列表，遍历字符串，将字符串的元素append to列表
2. 如果发现新追加的元素已经存在列表中，先判断此时的列表长度是否是历史最长，如果是就记录下来
3. 找到该元素在列表中的第一个index，然后把列表从返回的索引处切片，取后半部分
4. 判断如果此时记录的长度已经大于列表切片后半部分的长度与字符串剩下的长度之和，那么就不需要再往下遍历了，直接返回长度
5. 如果for循环正常结束，则需要判断此时的列表长度是否是最长，如果是就返回此时列表的长度，否则返回历史最长

代码如下（python3）

#-*- coding:utf-8 -*-
#Author: Bing Xu

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        len_result = 0
        temp = []
        for index in range(len(s)):
            temp.append(s[index])
            if temp.count(s[index]) > 1:
                if len(temp) - 1 >= len_result:
                    len_result = len(temp) - 1
                temp = temp[temp.index(s[index])+1:]
                if len_result >= len(s) - index - 1 + len(temp):
                    return len_result
        if len(temp) >= len_result:
            len_result = len(temp)
        return len_result

优秀题解

思路

这道题主要用到思路是：滑动窗口

• 什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

• 如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)

作者：powcai
链接：https://leetcode-cn.com/problems/two-sum/solution/hua-dong-chuang-kou-by-powcai/

代码如下

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

与优秀题解的差别

1. 我采用的是列表，优秀题解选择的是集合，在集合中查找的效率要远高于列表
2. 优秀题解采用双指针的思想，而我是通过对列表切片完成类似操作，消耗了很多的内存。

转载请注明来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。