詳解無(wú)重復(fù)字符的最長(zhǎng)子串

一、題目描述

給定一個(gè)字符串s，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。

示例 1:

輸入:s="abcabcbb"
輸出:3
解釋:因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是"abc"，所以其長(zhǎng)度為 3。

示例 2:

輸入:s="bbbbb"
輸出:1
解釋:因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是"b"，所以其長(zhǎng)度為 1。

示例 3:

輸入:s="pwwkew"
輸出:3
解釋:因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是"wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是子串的長(zhǎng)度，"pwke"是一個(gè)子序列，不是子串。

提示：

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

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

二、題目解析

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

具體操作如下：

1、定義需要維護(hù)的變量，對(duì)于此題來(lái)說(shuō)，要求是最大長(zhǎng)度，同時(shí)又涉及去重，因此需要一個(gè)哈希表。

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

3、窗口的右端位置從 0 開(kāi)始，可以一直移動(dòng)到尾部。

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

5、此時(shí)，滑動(dòng)窗口可以接納新增元素。

三、參考代碼

1、Java 代碼

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

//滑動(dòng)窗口模板化解題，五步走策略

//【1、定義需要維護(hù)的變量】

//對(duì)于此題來(lái)說(shuō)，要求是最大長(zhǎng)度
intmaxLen=0;

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

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

//窗口的左端位置從0開(kāi)始
intstart=0;

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

	

	2、C++ 代碼

	
classSolution{
public:
intlengthOfLongestSubstring(strings){

//滑動(dòng)窗口模板化解題，五步走策略

//【1、定義需要維護(hù)的變量】

//對(duì)于此題來(lái)說(shuō)，要求是最大長(zhǎng)度
intmaxLen=0;

//同時(shí)又涉及去重，因此需要一個(gè)哈希表
unordered_sethash;

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

//窗口的左端位置從0開(kāi)始
intstart=0;

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

	

	3、Python 代碼

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

#【1、定義需要維護(hù)的變量】

#對(duì)于此題來(lái)說(shuō)，要求是最大長(zhǎng)度
maxLen=0

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

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

#窗口的左端位置從0開(kāi)始
start=0

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

#【3、更新需要維護(hù)的變量,有的變量需要一個(gè)if語(yǔ)句來(lái)維護(hù)(比如最大最小長(zhǎng)度)】

#【4、如果題目的窗口長(zhǎng)度可變:這個(gè)時(shí)候一般涉及到窗口是否合法的問(wèn)題】
#如果當(dāng)前窗口不合法時(shí),用一個(gè)while去不斷移動(dòng)窗口左指針,從而剔除非法元素直到窗口再次合法

#如果哈希表中存儲(chǔ)了即將加入滑動(dòng)窗口的元素
whiles[end]inhash:

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

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

#窗口左端向右移動(dòng)
start+=1

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

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

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


	

	四、復(fù)雜度分析

	時(shí)間復(fù)雜度：O(N)，其中 N是字符串的長(zhǎng)度。左指針和右指針?lè)謩e會(huì)遍歷整個(gè)字符串一次。

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

	


	審核編輯：劉清