文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書
1. 問題描述
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
2. 求解
方法一
當(dāng)遍歷第i個字符時，需要判斷[index,i-1]的字符中是否有與s[i]重復(fù)的字符亥贸，如果字符s[j]與s[i]重復(fù)躬窜，index直接變?yōu)閖 + 1，重新計算不重復(fù)字符的數(shù)量炕置，如果[index,i-1]的字符中沒有與s[i]重復(fù)的字符荣挨，則不重復(fù)字符計數(shù)count++。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
int count = 0;
int index = 0;
//[index,i-1]中是否有與s[i]重復(fù)的字符
boolean flag = false;
for(int i = 0; i < s.length(); i++) {
flag = false;
char ch = s.charAt(i);
//如果s[j]與s[i]重復(fù)朴摊，index直接變?yōu)閖 + 1默垄，重新計算不重復(fù)字符數(shù)
for(int j = index; j < i; j++) {
if(s.charAt(j) == s.charAt(i)) {
flag = true;
index = j + 1;
count = i - j;
break;
}
}
if(!flag) {
count++;
if(count > max) {
max = count;
}
}
}
return max;
}
}
方法二
方法二的思路是看到有重復(fù)問題，首先想到哈希表甚纲，由于求解的是不重復(fù)子串口锭，因此需要將子串分為兩部分，一部分為(i介杆，n-1)鹃操，一部分為(j，i)春哨，如果s[i]不在(j荆隘，i)中，則將s[i]放入哈希表中赴背，同時計數(shù)器加1椰拒，如果s[i]在(j，i)中凰荚，則找到(j燃观，i)中與s[i]重復(fù)的字符ch，將其移除便瑟，當(dāng)然ch之前的字符也要將其從哈希表中移除缆毁，因為包含ch的子串一定與s[i]重復(fù)，每移除一個字符胳徽，j++积锅。重復(fù)上述過程，直至i到字符串最后养盗。每一個找的子串是從(j,i)不重復(fù)的最長子串缚陷。這里的j是方法一中的index。思路與方法一是一致的往核，區(qū)別是使用哈希表來判斷重復(fù)而不是使用循環(huán)箫爷。
public class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Character> map = new HashMap<Character, Character>();
int max = 0;
int count = 0;
int j = 0;
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
//如果有重復(fù)字符，逐個移除字符聂儒，直到移除了與第i個字符重復(fù)的字符
if(map.containsKey(ch)) {
while(map.containsKey(ch)) {
map.remove(s.charAt(j));
j++;
count--;
}
count++;
map.put(ch, ch);
}else {
map.put(ch, ch);
count++;
if(count > max) {
max = count;
}
}
}
return max;
}
}
備注：Leetcode測試時虎锚，發(fā)現(xiàn)方法一比方法二速度更快。
