😀前言
LeetCode上的“無(wú)重復(fù)字符的最長(zhǎng)子串”問(wèn)題要求我們找到給定字符串中不包含重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。這個(gè)問(wèn)題是一個(gè)典型的滑動(dòng)窗口技巧的應(yīng)用，需要有效地處理字符出現(xiàn)的情況來(lái)找到解決方案。
.
在本解決方案中，我們將探討兩種不同的算法實(shí)現(xiàn)來(lái)解決這個(gè)問(wèn)題。首先，我們將使用基本方法來(lái)解決問(wèn)題，然后進(jìn)一步優(yōu)化以獲得更好的時(shí)間復(fù)雜度。

🏠個(gè)人主頁(yè)：塵覺(jué)主頁(yè)

🧑個(gè)人簡(jiǎn)介：大家好，我是塵覺(jué)，希望我的文章可以幫助到大家，您的滿意是我的動(dòng)力😉😉

在csdn獲獎(jiǎng)榮譽(yù): 🏆csdn城市之星2名
????　????　????　????　????　????　????　????　💓Java全棧群星計(jì)劃top前5
????　????　????　????　????　????　????　????　🤗 端午大禮包獲得者
????　????　????　????　????　????　????　????　🥰阿里云專(zhuān)家博主
????　????　????　????　????　????　????　????　😉亞馬遜DyamoDB結(jié)營(yíng)

💕歡迎大家：這里是CSDN，我總結(jié)知識(shí)的地方，歡迎來(lái)到我的博客，感謝大家的觀看🥰
如果文章有什么需要改進(jìn)的地方還請(qǐng)大佬不吝賜教 先在次感謝啦😊

LeetCode 無(wú)重復(fù)字符的最長(zhǎng)子串 打敗100%的人

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

力扣官方題解

方法一：滑動(dòng)窗口

思路和算法

我們先用一個(gè)例子考慮如何在較優(yōu)的時(shí)間復(fù)雜度內(nèi)通過(guò)本題。

我們不妨以示例一中的字符串 abcabcbb為例，找出從每一個(gè)字符開(kāi)始的，不包含重復(fù)字符的最長(zhǎng)子串，那么其中最長(zhǎng)的那個(gè)字符串即為答案。對(duì)于示例一中的字符串，我們列舉出這些結(jié)果，其中括號(hào)中表示選中的字符以及最長(zhǎng)的字符串：

發(fā)現(xiàn)了什么？如果我們依次遞增地枚舉子串的起始位置，那么子串的結(jié)束位置也是遞增的！這里的原因在于，假設(shè)我們選擇字符串中的第 k 個(gè)字符作為起始位置，

并且得到了不包含重復(fù)字符的最長(zhǎng)子串的結(jié)束位置為 rk 。那么當(dāng)我們選擇第 k+1k+1 個(gè)字符作為起始位置時(shí)，首先從 k+1到 rk的字符顯然是不重復(fù)的，并且由于少了原本的第 k 個(gè)字符，我們可以嘗試?yán)^續(xù)增大 rk ，直到右側(cè)出現(xiàn)了重復(fù)字符為止。

這樣一來(lái)，我們就可以使用「滑動(dòng)窗口」來(lái)解決這個(gè)問(wèn)題了：

• 我們使用兩個(gè)指針表示字符串中的某個(gè)子串（或窗口）的左右邊界，其中左指針代表著上文中「枚舉子串的起始位置」，而右指針即為上文中的 rk ；

• 在每一步的操作中，我們會(huì)將左指針向右移動(dòng)一格，表示 我們開(kāi)始枚舉下一個(gè)字符作為起始位置，然后我們可以不斷地向右移動(dòng)右指針，但需要保證這兩個(gè)指針對(duì)應(yīng)的子串中沒(méi)有重復(fù)的字符。在移動(dòng)結(jié)束后，這個(gè)子串就對(duì)應(yīng)著 以左指針開(kāi)始的，不包含重復(fù)字符的最長(zhǎng)子串。我們記錄下這個(gè)子串的長(zhǎng)度；

• 在枚舉結(jié)束后，我們找到的最長(zhǎng)的子串的長(zhǎng)度即為答案。

判斷重復(fù)字符

在上面的流程中，我們還需要使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)判斷 是否有重復(fù)的字符，常用的數(shù)據(jù)結(jié)構(gòu)為哈希集合

在左指針向右移動(dòng)的時(shí)候，我們從哈希集合中移除一個(gè)字符，在右指針向右移動(dòng)的時(shí)候，我們往哈希集合中添加一個(gè)字符。

 public int lengthOfLongestSubstring(String s) {// 哈希集合，記錄每個(gè)字符是否出現(xiàn)過(guò)Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指針，初始值為 -1，相當(dāng)于我們?cè)谧址淖筮吔绲淖髠?cè)，還沒(méi)有開(kāi)始移動(dòng)int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指針向右移動(dòng)一格，移除一個(gè)字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不斷地移動(dòng)右指針occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 個(gè)字符是一個(gè)極長(zhǎng)的無(wú)重復(fù)字符子串ans = Math.max(ans, rk - i + 1);}return ans;}

優(yōu)秀思路

這個(gè)打敗100%

自己思路

首先因?yàn)樽帜副碜畲驛SCLL為128所以我們就初始化128個(gè)空間并且假設(shè)全部沒(méi)有出現(xiàn)為0，但是在數(shù)組中我們是0開(kāi)頭的所以什么設(shè)置為-1

其次我們?cè)O(shè)置 長(zhǎng)度0 最大個(gè)數(shù)0 開(kāi)始位置0

重點(diǎn)

我們開(kāi)始循環(huán) aabcd

i 代表我們是到那個(gè)字符了

首先我們讀取每個(gè)字符的ASCLL值 賦值到index

然后我們開(kāi)始計(jì)算 起始位置 如果這個(gè)字符出現(xiàn)過(guò)我們就更新起始實(shí)位置 last[index]上一次出現(xiàn)的位置 +1是 代表字符串內(nèi)字符不能重復(fù)，所以要從上一次出現(xiàn)位置的下一個(gè)位置開(kāi)始

如aabcd 第一個(gè)a 出現(xiàn)過(guò)一次 所以在 last[index] 的位置為 0 因?yàn)槌霈F(xiàn)過(guò)一次了所以我們就從 第二個(gè)a 開(kāi)始 就是 last[index]+1 以此類(lèi)推

再是 我們比較 最大子串和 當(dāng)前位置 i - 開(kāi)始位置看誰(shuí)最長(zhǎng) 注意這個(gè)加1是代表次數(shù) 因?yàn)槲覀兪菑?開(kāi)始 但是計(jì)數(shù)是從1開(kāi)始 所以要+1

最后 我們記錄這個(gè)字符在這個(gè)字符串中的位置 注意這個(gè)是字符串的位置是從0開(kāi)始的

總結(jié)

要注意 計(jì)數(shù) 和在字符串 的位置 一個(gè)是從0 開(kāi)始 一個(gè)是從 1開(kāi)始 這就是為什么需要i - start + 1需要+1的原因

    public int lengthOfLongestSubstring(String s) {// 記錄字符上一次出現(xiàn)的位置int[] last = new int[128];for(int i = 0; i < 128; i++) {last[i] = -1;}int n = s.length();int res = 0;int start = 0; // 窗口開(kāi)始位置for(int i =0 ; i < n; i++) {int index = s.charAt(i);start = Math.max(start, last[index] + 1);res   = Math.max(res, i - start + 1);last[index] = i;}return res;}

再優(yōu)化一下

大體邏輯是差不多的這里注意說(shuō)一下區(qū)別

這里沒(méi)有賦值是利用了java在初始化數(shù)組的時(shí)候是默認(rèn)分配0

last[index] = i+1; 代表著這個(gè)字符出現(xiàn)的位置 比如 aabcd 第一個(gè)a 它的位置是 i+1=1次 到第二個(gè)a的時(shí)候就是 i=1
所以 start = Math.max(start, last[index])直接是從1開(kāi)始 然后重新記錄a的位置是 i+1=2 以此類(lèi)推
注意這個(gè)是從 1開(kāi)始的 不是0 包括后面 res也是從1開(kāi)始 不是0

總結(jié)

要注意區(qū)分 統(tǒng)計(jì) 和 數(shù)組位置 以及 從1開(kāi)始的位置

// 記錄字符上一次出現(xiàn)的位置int[] last = new int[128];
//        for(int i = 0; i < 128; i++) {
//            last[i] = -1;
//        }int n = s.length();int res = 0;int start = 0; // 窗口開(kāi)始位置for(int i = 0; i < n; i++) {int index = s.charAt(i);start = Math.max(start, last[index]);res   = Math.max(res, i + 1 - start );last[index] = i+1;}return res;

😄總結(jié)

基本實(shí)現(xiàn)：

1. 初始化大小為128的數(shù)組last（表示ASCII字符）來(lái)跟蹤每個(gè)字符上次出現(xiàn)的索引位置。將last中的所有元素初始化為-1，表示尚未見(jiàn)過(guò)任何字符。

2. 從左到右遍歷輸入字符串s。

3. 對(duì)于s中索引為i的字符，計(jì)算其ASCII值并將其存儲(chǔ)在index變量中。

4. 更新start變量，使其成為當(dāng)前值和last[index] + 1中的較大者。這一步確保start表示當(dāng)前不包含重復(fù)字符的子串的起始位置。

5. 更新res變量，使其成為當(dāng)前值和i + 1 - start中的較大者。這一計(jì)算找到了當(dāng)前不包含重復(fù)字符的子串的長(zhǎng)度，并與先前的最大長(zhǎng)度進(jìn)行比較。

6. 更新last[index]為i + 1，記錄字符在字符串中的最近位置。

7. 重復(fù)步驟3-6，直到處理完整個(gè)字符串。

8. 最終的res值將表示輸入字符串s中不包含重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。

優(yōu)化實(shí)現(xiàn)：

1. 優(yōu)化版本的解決方案消除了不必要的last數(shù)組初始化，并相應(yīng)地調(diào)整了計(jì)算。還利用了Java默認(rèn)使用零初始化數(shù)組的特性。

2. 通過(guò)進(jìn)行這些優(yōu)化，代碼變得更加簡(jiǎn)潔，并且在內(nèi)存使用和代碼簡(jiǎn)潔性方面都得到了改善。

3. 這兩種實(shí)現(xiàn)都提供了正確的答案，但優(yōu)化版本在內(nèi)存使用和代碼簡(jiǎn)潔性方面都具有更高的效率。

這些實(shí)現(xiàn)為解決LeetCode上的“無(wú)重復(fù)字符的最長(zhǎng)子串”問(wèn)題提供了清晰而高效的方法，展示了滑動(dòng)窗口技巧和字符出現(xiàn)情況跟蹤的應(yīng)用。

😁熱門(mén)專(zhuān)欄推薦
想學(xué)習(xí)vue的可以看看這個(gè)

java基礎(chǔ)合集

數(shù)據(jù)庫(kù)合集

redis合集

nginx合集

linux合集

手寫(xiě)機(jī)制

微服務(wù)組件

spring

springMVC

mybits

等等等還有許多優(yōu)秀的合集在主頁(yè)等著大家的光顧感謝大家的支持

🤔歡迎大家加入我的社區(qū) 塵覺(jué)社區(qū)

文章到這里就結(jié)束了，如果有什么疑問(wèn)的地方請(qǐng)指出，諸佬們一起來(lái)評(píng)論區(qū)一起討論😁
希望能和諸佬們一起努力，今后我們一起觀看感謝您的閱讀🍻
如果幫助到您不妨3連支持一下，創(chuàng)造不易您們的支持是我的動(dòng)力🤞