前段時(shí)間和小米的某面試官聊天。因?yàn)槲乙恢痹谧?算法文章 的更新，就多聊了幾句算法方面的知識(shí)。

并且在聊天過程中獲得了一個(gè)“重要情報(bào)”：只要他來面試，基本上每次的算法題，都會(huì)去考察關(guān)于 子串和子序列 的問題。

的確，如果說哪種算法更容易在面試中被考察到，子串、子序列 的問題想必能排在 數(shù)一數(shù)二 的位置上。

---

在之前的 「動(dòng)態(tài)規(guī)劃」 系列文章中，我們講到了 最長公共子序列 和 最長回文子序列 的問題，今天我們繼續(xù)來探討力扣上一個(gè)關(guān)于 子串 的問題。

3.無重復(fù)字符的最長子串

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

示例 1：

輸入： s = “abcabcbb”

輸出： 3

解釋： 因?yàn)闊o重復(fù)字符的最長子串是 “abc”，所以其長度為 3。

示例 2:

輸入： s = “bbbbb”

輸出： 1

解釋： 因?yàn)闊o重復(fù)字符的最長子串是 “b”，所以其長度為 1。

---

小 tips： 要注意分清楚，子串 和 子序列 的區(qū)別喲~

• 子串： 必須連續(xù)
• 子序列： 可以不連續(xù)

思路分析

這里回顧一個(gè) 重要思想 ，對(duì)于 子串和子序列 的題目，可以按如下方式進(jìn)行思考：

考慮 以 i 位置為結(jié)尾 的情況下，答案如何選取

該思想在 數(shù)組求和-2 這篇文章中也有提到哦~

因此，對(duì)于本題來說：

• 考慮若以每個(gè)位置作為結(jié)尾時(shí)，子串能夠向前延伸多長，最長的子串長度就是我們要求的答案。

那么問題就進(jìn)一步轉(zhuǎn)化為：

• 在給定一個(gè)結(jié)尾的字符時(shí)，應(yīng)該如何向前延伸呢，延伸的長度會(huì)受到哪些因素影響呢？

稍加思考：

1. 由于要找到最長無重復(fù)的子串，因此一定與該字符 相同的前一個(gè)字符 的位置有關(guān)。

• 例如，假設(shè) 3 到 8 下標(biāo)之間沒有再出現(xiàn)a字符，則以 9 號(hào)下標(biāo)為結(jié)尾的a字符往前延伸的距離最多只能到下標(biāo) 3 處。

2. 除了因素 1 外，也與該字符的 前一個(gè)字符 向前延伸的位置有關(guān)。

• 同樣例子，假設(shè)下標(biāo)為 9 的a字符的前一個(gè)字符是b， 6 到 7 下標(biāo)之間沒有再出現(xiàn)b字符，則以 8 號(hào)下標(biāo)為結(jié)尾的b字符往前延伸的距離最多只能到下標(biāo) 6 處。
• 進(jìn)而導(dǎo)致了下標(biāo)為 9 的a字符往前延伸的距離最多也只能到下標(biāo) 6 處。

確定了影響最終答案的因素后，思路便豁然開朗了：

兩個(gè)因素中結(jié)果較大的下標(biāo)即為該位置所能擴(kuò)充的最遠(yuǎn)距離。

1. 需要解決能夠找到前一個(gè)相同字符下標(biāo)的方法；（使用map）
2. 設(shè)置存儲(chǔ)前一個(gè)字符 最遠(yuǎn)能夠向前擴(kuò)充的下標(biāo) 變量。
3. 取 1，2 中 較大的下標(biāo) 即為該位置字符的答案。

代碼

public static int lengthOfLongestSubstring(String s) {if (s == null || s.equals("")) {return 0;}char[] str = s.toCharArray();// 這里并沒有直接使用 map , 與 map 功能類似// 該 map 數(shù)組中存放的是 該字符 上一次出現(xiàn)時(shí) 的 下標(biāo)int[] map = new int[256];for (int i = 0; i < 256; i++) {map[i] = -1;}// 最新的答案（即此前最長的子串長度）int len = 0;// 前一個(gè)字符能夠向前擴(kuò)充的最遠(yuǎn)位置在哪int pre = -1;// 當(dāng)前位置字符能夠向前擴(kuò)充的最遠(yuǎn)位置在哪int cur = 0;for (int i = 0; i != str.length; i++) {// 取兩個(gè)因素中的最大值pre = Math.max(pre, map[str[i]]);// 此時(shí)能夠擴(kuò)充的最大距離cur = i - pre;// 更新答案len = Math.max(len, cur);// 更新最新該字符出現(xiàn)的位置map[str[i]] = i;}return len;
}

理解了本題的思想之后，上述代碼也不難看懂。小伙伴們仔細(xì)思考一下喲！！！

寫在最后

前面的算法文章，更新了許多 專題系列 。包括：滑動(dòng)窗口、動(dòng)態(tài)規(guī)劃、加強(qiáng)堆、二叉樹遞歸套路 等。

還沒讀過的小伙伴可以關(guān)注同名號(hào)，在主頁中點(diǎn)擊對(duì)應(yīng)鏈接查看哦~

接下來的一段時(shí)間，將持續(xù) 「力扣高頻題」 系列文章，想刷 力扣高頻題 的小伙伴也可以關(guān)注一波哦 ~

~ 點(diǎn)贊 ~ 關(guān)注 ~ 星標(biāo) ~ 不迷路 ~！！！

關(guān)注
回復(fù)「ACM紫書」獲取 ACM 算法書籍 ~
回復(fù)「算法導(dǎo)論」獲取 算法導(dǎo)論第3版 ~

在看 + 轉(zhuǎn)發(fā)

讓你的小伙伴們一起來學(xué)算法吧！！