文章來源： 飯飯的Python學習之路

作者： 一粒米飯

今天要挑戰的是“無重復字符的最長子串”。

難度：中等

題目描述：

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

示例1:

輸入:?"abcabcbb"輸出:?3?解釋:?因為無重復字符的最長子串是?"abc"，所以其長度為 3。

示例2:

輸入:?"bbbbb"輸出:?1解釋:?因為無重復字符的最長子串是?"b"，所以其長度為 1。

示例3:

輸入:?"pwwkew"輸出:?3解釋:?因為無重復字符的最長子串是?"wke"，所以其長度為 3。???請注意，你的答案必須是?子串?的長度，"pwke"?是一個子序列，不是子串。

題目原始鏈接

解題思路：

這道題的解題思路主要是利用滑動窗口思維。

什么是滑動窗口

滑動窗口作為雙指針算法的一種特殊形式，在日常算法中尤其是字符串匹配查詢中經常用到。

其基本思想是通過使用特定大小的子列表，在遍歷完整列表的同時進行特定的操作，以達到降低了循環的嵌套深度。

滑動窗口的基本邏輯如下：

使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引閉區間 [left, right] 稱為一個「窗口」。

先不斷地增加 right 指針擴大窗口 [left, right]，直到窗口符合要求

停止增加 right，轉而不斷增加 left 指針縮小窗口 [left, right]，直到窗口中的字符串不再符合要求。同時，每次增加 left，我們都要更新一輪結果。

重復第 2 和第 3 步，直到 right 到達盡頭。

代碼實現：

class?Solution:????def?lengthOfLongestSubstring(self,?s:?str)?->?int:????????w?=?""????????l?=?0????????max_l?=?0????????for?c?in?s:????????????if?c?in?w:????????????????left?=?w.index(c)?+?1????????????????w?=?w[left:]????????????????l?-=?left????????????w?+=?c????????????l?+=?1????????????if?l?>?max_l:????????????????max_l?=?l????????return?max_l

結果:

除了無重復字符的最長子串，滑動窗口還可以用來解決連續子數組的最大和、和為特定值的連續正整數序列、長度最小的子數組等問題。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的c++ 数组的输入遇到特定字符停止输入_滑动窗口思维--挑战“无重复字符的最长子串”的全部內容，希望文章能夠幫你解決所遇到的問題。

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