文章目錄
- 題目
-
- 3. Longest Substring Without Repeating Characters
- 分析
-
- 思路1：簡單周遊
- 思路2：設定移動視窗
- 題解
-
- java實作1
- java實作2
- java實作3
- c++實作
題目
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
給定字元串，求出不含重複字元的最長連續子串。
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
分析
本題要求給出一個方法lengthOfLongestSubstring，方法要求：
傳入一個參數：字元串s。
傳出s中不含重複字元的最長連續子串。
思路1：簡單周遊
先給出一種基本思路：先暴力再優化
假定字元串s的長度為n，我們要找到最長的連續不重複子串，就從長度為n的字元串找起。如果中間出現重複字元，再找長度為n-1的字元串，然後是n-2的……以此類推。
附上實作該思路的java代碼：
public int lengthOfLongestSubstring(String s) {
int length = s.length();
for(int len=length;len>=1;len--){//len：截取的字元串長度
for(int head=0;head<=length-len;head++){//head：截取的字元串的首位
String substring = s.substring(head,head+len);//截取的字元串
char [] subchars = substring.toCharArray();//将截取字元串轉為char數組
int charLen = subchars.length;
boolean duplications = false;//判斷字串中是否出現字元重複
for(int i=0;i<charLen-1;i++){
for(int j=i+1;j<charLen;j++){
if(subchars[j]==subchars[i]){
duplications = true;
break;
}
}
if(duplications)break;
}
if(!duplications){
return len;
}
}
}
return 0;
}
但是如果這樣就能解決了，這道題也就不是
Medium
難度的了~
那麼如何優化呢：
我們可以考慮将len的初始值優化。len的最大可能值可以從“字元串長度”縮減為“字元串中不重複字元的個數”。
以下為優化後代碼：
public int lengthOfLongestSubstring(String s) {
int length = s.length();
//先統計不同字元數，以提升算法總體速度
int characters = 1;
char [] chars = s.toCharArray();
boolean flag = false;//判斷是否出現重複
for(int i=1;i<length;i++){
flag = false;
for(int j=0;j<i;j++){
if(chars[i] == chars[j]){
flag = true;
continue;
}
}
if(!flag)characters++;
}
//以下隻需考慮長度≤characters的字元串即可
for(int len=characters;len>=1;len--){//len：截取的字元串長度
for(int head=0;head<=length-len;head++){//head：截取的字元串的首位
String substring = s.substring(head,head+len);//截取的字元串
char [] subchars = substring.toCharArray();//将截取字元串轉為char數組
int charLen = subchars.length;
boolean duplications = false;//判斷字串中是否出現字元重複
for(int i=0;i<charLen-1;i++){
for(int j=i+1;j<charLen;j++){
if(subchars[j]==subchars[i]){
duplications = true;
break;
}
}
if(duplications)break;
}
if(!duplications){
return len;
}
}
}
return 0;
}
成功AC。
思路2：設定移動視窗
我們維護兩個變量：
left：移動視窗的左邊界
res：字元不重複的連續子串的最大長度
而移動視窗的右邊界，我們放在循環中周遊（依次加1）
例如字元串abcdbfcgh，思路圖解如下：
從最左端開始設定移動視窗：
而後逐漸向右擴充（在不遇到重複字元的前提下）：
在這裡我們遇到了b，發現和前面出現了重複。
此時把左邊界left更新為原來b的下标（也就是1），移動整個視窗：
而後繼續向右擴充：
後面遇到c，又出現重複問題。跟之前一樣的方法解決。将left更新為原來c的下标2，移動視窗：
繼續擴充：
最後得到res的最大值：6。
代碼請參考題解部分。
題解
java實作1
public int lengthOfLongestSubstring(String s) {
int length = s.length();
//先統計不同字元數，以提升算法總體速度
int characters = 1;
char [] chars = s.toCharArray();
boolean flag = false;//判斷是否出現重複
for(int i=1;i<length;i++){
flag = false;
for(int j=0;j<i;j++){
if(chars[i] == chars[j]){
flag = true;
continue;
}
}
if(!flag)characters++;
}
//以下隻需考慮長度≤characters的字元串即可
for(int len=characters;len>=1;len--){//len：截取的字元串長度
for(int head=0;head<=length-len;head++){//head：截取的字元串的首位
String substring = s.substring(head,head+len);//截取的字元串
char [] subchars = substring.toCharArray();//将截取字元串轉為char數組
int charLen = subchars.length;
boolean duplications = false;//判斷字串中是否出現字元重複
for(int i=0;i<charLen-1;i++){
for(int j=i+1;j<charLen;j++){
if(subchars[j]==subchars[i]){
duplications = true;
break;
}
}
if(duplications)break;
}
if(!duplications){
return len;
}
}
}
return 0;
}
java實作2
public int lengthOfLongestSubstring(String s) {
int[] m = new int[256];//存儲字元出現的位置，例如m['A']=0,說明字元A出現在下标為0的位置
Arrays.fill(m, -1);
int res = 0, left = -1;
for (int i = 0; i < s.length(); ++i) {
left = Math.max(left, m[s.charAt(i)]);
m[s.charAt(i)] = i;
res = Math.max(res, i - left);
}
return res;
}
java實作3
//與“java實作2”是幾乎完全一樣的思路，隻不過用hashset
public int lengthOfLongestSubstring(String s) {
int res = 0, left = 0, right = 0;
HashSet<Character> t = new HashSet<Character>();
while (right < s.length()) {
if (!t.contains(s.charAt(right))) {
t.add(s.charAt(right++));
res = Math.max(res, t.size());
} else {
t.remove(s.charAt(left++));
}
}
return res;
}
c++實作
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int m[256] = {0}, res = 0, left = 0;
for (int i = 0; i < s.size(); ++i) {
if (m[s[i]] == 0 || m[s[i]] < left) {
res = max(res, i - left + 1);
} else {
left = m[s[i]];
}
m[s[i]] = i + 1;
}
return res;
}
};