一、題目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

0 <= s.length <= 5 * 10^4

s由英文字母、數(shù)字、符號和空格組成

二、題目解析

很經(jīng)典的滑動窗口的題目。

具體操作如下：

1、定義需要維護的變量，對于此題來說，要求是最大長度，同時又涉及去重，因此需要一個哈希表。

2、定義窗口的首尾端 (start, end)， 然后滑動窗口。

3、窗口的右端位置從 0 開始，可以一直移動到尾部。

4、如果哈希表中存儲了即將加入滑動窗口的元素，那么需要不斷的把窗口左邊的元素移除窗口。

5、此時，滑動窗口可以接納新增元素。

三、參考代碼

1、Java 代碼

//登錄AlgoMooc官網(wǎng)獲取更多算法圖解
//https://www.algomooc.com
//作者：程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢吳師兄呀
//無重復字符的最長子串（LeetCode 3）：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
classSolution{
publicintlengthOfLongestSubstring(Strings){

//滑動窗口模板化解題，五步走策略

//【1、定義需要維護的變量】

//對于此題來說，要求是最大長度
intmaxLen=0;

//同時又涉及去重，因此需要一個哈希表
HashSethash=newHashSet();

//【2、定義窗口的首尾端(start,end)，然后滑動窗口】

//窗口的左端位置從0開始
intstart=0;

//窗口的右端位置從0開始，可以一直移動到尾部
for(intend=0;end

	

	2、C++ 代碼

	
classSolution{
public:
intlengthOfLongestSubstring(strings){

//滑動窗口模板化解題，五步走策略

//【1、定義需要維護的變量】

//對于此題來說，要求是最大長度
intmaxLen=0;

//同時又涉及去重，因此需要一個哈希表
unordered_sethash;

//【2、定義窗口的首尾端(start,end)，然后滑動窗口】

//窗口的左端位置從0開始
intstart=0;

//窗口的右端位置從0開始，可以一直移動到尾部
for(intend=0;end

	

	3、Python 代碼

	
classSolution:
deflengthOfLongestSubstring(self,s:str)->int:
#滑動窗口模板化解題，五步走策略

#【1、定義需要維護的變量】

#對于此題來說，要求是最大長度
maxLen=0

#同時又涉及去重，因此需要一個哈希表
hash=set()

#【2、定義窗口的首尾端(start,end)，然后滑動窗口】

#窗口的左端位置從0開始
start=0

#窗口的右端位置從0開始，可以一直移動到尾部
forendinrange(len(s)):

#【3、更新需要維護的變量,有的變量需要一個if語句來維護(比如最大最小長度)】

#【4、如果題目的窗口長度可變:這個時候一般涉及到窗口是否合法的問題】
#如果當前窗口不合法時,用一個while去不斷移動窗口左指針,從而剔除非法元素直到窗口再次合法

#如果哈希表中存儲了即將加入滑動窗口的元素
whiles[end]inhash:

#那么需要不斷的把窗口左邊的元素移除窗口

#把s.charAt(start)移除記錄
hash.remove(s[start])

#窗口左端向右移動
start+=1

#此時，滑動窗口可以接納s.charAt(end)
hash.add(s[end])

#維護變量maxLen
maxLen=max(maxLen,end-start+1)

#【5、返回所需要的答案】
returnmaxLen


	

	四、復雜度分析

	時間復雜度：O(N)，其中 N是字符串的長度。左指針和右指針分別會遍歷整個字符串一次。

	空間復雜度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出現(xiàn)的字符），∣Σ∣ 表示字符集的大小。

	


	審核編輯：劉清