?

題目描述

?

給定一個(gè)字符串，找出不含有重復(fù)字符的最長子串的長度。

示例：

給定?"abcabcbb"?，沒有重復(fù)字符的最長子串是?"abc"?，那么長度就是3。

給定?"bbbbb"?，最長的子串就是?"b"?，長度是1。

給定?"pwwkew"?，最長子串是?"wke"?，長度是3。請(qǐng)注意答案必須是一個(gè)子串，"pwke"?是?子序列??而不是子串。

?

解題思路

?

采用雙指針的思想，維護(hù)兩個(gè)指針i、j，i為無重復(fù)子串的右端點(diǎn)，j為無重復(fù)子串的左端點(diǎn)，這樣此子串的長度為i-j+1.再用哈希的思想維護(hù)一個(gè)大小為128的數(shù)組，其下標(biāo)代表ASCII碼共128個(gè)字符，下標(biāo)對(duì)應(yīng)的值記錄當(dāng)前字符最后一次出現(xiàn)位置的后一個(gè)位置。這樣做的目的是在子串中遇到重復(fù)的字符時(shí)，下一個(gè)無重復(fù)子串一定不包含左邊的重復(fù)字符，所以直接從左邊重復(fù)字符的后一個(gè)位置繼續(xù)尋找。令哈希數(shù)組初始全為0，這樣i每次向后走一步,

• 若i指向的字符在j~i-1的字符串中出現(xiàn)，即哈希數(shù)組中當(dāng)前字符下標(biāo)對(duì)應(yīng)位置大于j，則j指向左邊重復(fù)字符的后一個(gè)位置，否則j不動(dòng)
• 接著計(jì)算當(dāng)前無重復(fù)子串的長度并更新最大長度
• 最后修改哈希數(shù)組，使當(dāng)前字符下標(biāo)對(duì)應(yīng)值為當(dāng)前位置+1

?

代碼

?

1 class Solution { 2 public: 3 int lengthOfLongestSubstring(string s) { 4 int idx[128] = {0}; 5 int maxLen = 0; 6 for(int i = 0, j = 0; i < s.size(); i++){ 7 j = max(idx[s[i]], j); 8 maxLen = max(i-j+1, maxLen); 9 idx[s[i]] = i+1; 10 } 11 return maxLen; 12 } 13 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/wmx24/p/9141928.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode 3. 无重复字符的最长子串（Longest Substring Without Repeating Characters）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。