About
今天是刷LeetCode的第五天轮洋，不敢稱之為挑戰(zhàn)了，因?yàn)榘l(fā)現(xiàn)自己還是太弱小抬旺，很久不寫代碼腦子都銹了弊予，每次做出的題解在性能上都和大神有很大的差距，但是為了提高我的代碼質(zhì)量开财，我必須堅(jiān)持下去汉柒！
無重復(fù)字符的最長子串
題目描述
給定一個字符串误褪，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"碾褂，所以其長度為 3兽间。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1正塌。
示例 3:
輸入: "pwwkew"
輸出: 3
解題思路
- 創(chuàng)建一個空列表嘀略，遍歷字符串，將字符串的元素
append to列表 - 如果發(fā)現(xiàn)新追加的元素已經(jīng)存在列表中传货，先判斷此時(shí)的列表長度是否是歷史最長屎鳍，如果是就記錄下來
- 找到該元素在列表中的第一個
index，然后把列表從返回的索引處切片问裕，取后半部分 - 判斷如果此時(shí)記錄的長度已經(jīng)大于列表切片后半部分的長度與字符串剩下的長度之和，那么就不需要再往下遍歷了孵坚，直接返回長度
- 如果
for循環(huán)正常結(jié)束粮宛，則需要判斷此時(shí)的列表長度是否是最長，如果是就返回此時(shí)列表的長度卖宠，否則返回歷史最長
代碼如下（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
優(yōu)秀題解
思路
這道題主要用到思路是：滑動窗口
- 什么是滑動窗口巍杈？
其實(shí)就是一個隊(duì)列,比如例題中的 abcabcbb，進(jìn)入這個隊(duì)列（窗口）為 abc 滿足題目要求扛伍，當(dāng)再進(jìn)入 a筷畦，隊(duì)列變成了 abca，這時(shí)候不滿足要求刺洒。所以鳖宾，我們要移動這個隊(duì)列！
- 如何移動逆航？
我們只要把隊(duì)列的左邊的元素移出就行了鼎文，直到滿足題目要求！一直維持這樣的隊(duì)列因俐，找出隊(duì)列出現(xiàn)最長的長度時(shí)候拇惋，求出解！
時(shí)間復(fù)雜度：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
與優(yōu)秀題解的差別
- 我采用的是列表抹剩，優(yōu)秀題解選擇的是集合撑帖，在集合中查找的效率要遠(yuǎn)高于列表
- 優(yōu)秀題解采用雙指針的思想，而我是通過對列表切片完成類似操作澳眷，消耗了很多的內(nèi)存胡嘿。
轉(zhuǎn)載請注明來源
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)境蔼，非商業(yè)轉(zhuǎn)載請注明出處灶平。
