---

前言

各位讀者好, 我是小陳, 這是我的個(gè)人主頁(yè), 希望我的專欄能夠幫助到你:
📕 JavaSE基礎(chǔ): 基礎(chǔ)語(yǔ)法, 類和對(duì)象, 封裝繼承多態(tài), 接口, 綜合小練習(xí)圖書管理系統(tǒng)等
📗 Java數(shù)據(jù)結(jié)構(gòu): 順序表, 鏈表, 堆, 二叉樹(shù), 二叉搜索樹(shù), 哈希表等
📘 JavaEE初階: 多線程, 網(wǎng)絡(luò)編程, TCP/IP協(xié)議, HTTP協(xié)議, Tomcat, Servlet, Linux, JVM等(正在持續(xù)更新)

一、長(zhǎng)度最小子數(shù)組

1, 題目

OJ鏈接

一般來(lái)說(shuō), 如果我們研究的對(duì)象是 “連續(xù)的區(qū)間” 就可以考慮滑動(dòng)窗口

滑動(dòng)窗口其實(shí)就是"同向雙指針", 滑動(dòng)窗口的特點(diǎn)是, 前后兩個(gè)指針不會(huì)回退, 并且窗口總是向前滑動(dòng), 窗口不是固定大小的, 可能邊長(zhǎng)也可能變短, 如果你在分析題目的時(shí)候發(fā)現(xiàn)了這些特征, 那就基本是滑動(dòng)窗口的解法了

---

2, 思路分析

暴力解法 : 兩層 for 循環(huán), 先固定第一個(gè)字符, 然后遍歷第二個(gè)字符, 每遍歷到一個(gè)字符就判斷是否已經(jīng)出現(xiàn)過(guò), 利用暴力枚舉, 尋找出所有子序列

但這一定會(huì)超時(shí), 有沒(méi)有優(yōu)化的方案呢?

• 1, 使用哈希表, 定義一個(gè) set, 用于檢查當(dāng)前字符是否已經(jīng)出現(xiàn)過(guò)
• 2 , 定義 maxLen, 用于記錄目前最大長(zhǎng)度
• 3, 定義 left 和 right 指針, 初始位置都從0開(kāi)始, left 用于標(biāo)記子序列的左邊界, right 用于標(biāo)記子序列的右邊界

前期依然是暴力枚舉找到第一個(gè)滿足條件的子數(shù)組, 但接下來(lái)就不需要接著暴力枚舉, 如圖所示

增大窗口對(duì)應(yīng)的操作就是 right++, 縮小窗口的操作就是 left++

right 每指向一個(gè)字符, 就判斷是否已經(jīng)存在

• 如果不存在, 直接增大窗口即可
• 如果已經(jīng)存在, 就 要找到 窗口中的這個(gè)已出現(xiàn)的字符, 并將它排除在窗口之外

需要注意的是, " 要找到 窗口中的這個(gè)已出現(xiàn)的字符 " 這個(gè)操作是一個(gè)循環(huán), 但上圖中沒(méi)有表現(xiàn)出來(lái), 如下圖所示

綜上所述, 可以發(fā)現(xiàn), left 和 right 指針全程沒(méi)有回退, 并且窗口即會(huì)邊長(zhǎng)也會(huì)變短, 但一直在向前滑動(dòng), 這就是滑動(dòng)窗口的特性

---

3, 代碼

	public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>();int left = 0;int right = 0;int maxLen = 0;while(right < s.length()){char ch = s.charAt(right);if(set.contains(ch) ){while(s.charAt(left) != ch) {set.remove(s.charAt(left));left++;}left++;}set.add(ch);maxLen = Math.max(maxLen, right - left + 1);right++;}return maxLen;}