前言

開始刷leetcode，保證平均每天一道題吧，學學別人的思路，提高編程技術。

目錄

文章目錄

• 前言
• 目錄
• 正文
• 問題3
• 舉例
• 分析
• • 什么是滑動窗口？
  • 如何移動？
• 代碼

正文

問題3

給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。

舉例

輸入：“abcabcbb”
輸出：因為無重復字符的最長子串是 “abc”，所以其長度為 3。

分析

問題的一個核心要點是子串而不是子序列，子序列可以直接用set求解，子串則要求元素是連續的。
這道題主要用到思路是：滑動窗口

什么是滑動窗口？

其實就是一個隊列,比如例題中的 abcabcbb，進入這個隊列（窗口）為 abc 滿足題目要求，當再進入 a，隊列變成了 abca，這時候不滿足要求。所以，我們要移動這個隊列！

如何移動？

我們只要把隊列的左邊的元素移出就行了，直到滿足題目要求！
一直維持這樣的隊列，找出隊列出現最長的長度時候，求出解！
時間復雜度：O(n)
空間復雜度：

代碼

實現過程中利用了，集合的特性，自動消除重復元素。

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

總結

以上是生活随笔為你收集整理的leetcode刷题实录：3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。