Given a string, find the length of the longest substring without repeating characters.給定一個字符串蛮艰，找到字符串中的最長無重復(fù)子串腋腮，返回該子串的長度
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.
Code
- 暴力解法
思路
枚舉所有子串，逐一判斷每一子串是否是無重復(fù)子串壤蚜，如果是無重復(fù)子串即寡，則與當(dāng)前已知的最長的無重復(fù)子串比較，如果比其更長袜刷，則需要更新子串長度
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
// i 是子串的起點聪富，j - 1 是子串的終點
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (allUnique(s, i, j)) {
ans = Math.max(ans, j - i);
}
}
}
return ans;
}
// 用 set 來判斷是否有重復(fù)元素
public boolean allUnique(String s, int start, int end) {
Set<Character> set = new HashSet<>();
for (int i = start; i < end; i++) {
Character ch = s.charAt(i);
if (set.contains(ch)) {
return false;
}
set.add(ch);
}
return true;
}
}
時間復(fù)雜度： O(n ^ 3)
空間復(fù)雜度：set 的大小
- 滑動窗口(兩根指針的前向型應(yīng)用)
思路
如果 i 到 j-1 沒有重復(fù)元素，則當(dāng) j++ 后只需判斷 j 位置元素是否在 i 到 j-1 出現(xiàn)過著蟹，無需重復(fù)判斷i 到 j-1 中是否有重復(fù)元素墩蔓，而用一個 set 就可以在 O(1) 的時間內(nèi)判斷出 s.charAt(j) 是否出現(xiàn)過
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
// j 在添加到 set 后又執(zhí)行了一次 j++ 操作
// 所以本來的 j - i+ 1的寫法就變成了 j - i
// 滑動窗口范圍從 i 到 j - 1 并不包含 j
ans = Math.max(ans, j - i);
}
else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
時間復(fù)雜度：O(2n) 近似于 O(n)
空間復(fù)雜度：O(k) k 為 set 大小
- 用 HashMap 優(yōu)化滑動窗口
思路
以字母為鍵梢莽，下標(biāo)為值，建立哈希表钢拧，如果 s[ j ] 在[ i, j ) 范圍內(nèi)有有和它一樣的重復(fù)字母s[ j' ]蟹漓， 則 i 可以直接跳過 [ i, j' ] 范圍內(nèi)的所有元素，直接從 j' + 1 開始源内，優(yōu)化了滑動窗口一點點移動 i 的做法
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
// current index of character
Map<Character, Integer> map = new HashMap<>();
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
// j 從 0 開始葡粒，區(qū)間范圍 [i, j)，所以要對應(yīng) j + 1膜钓；
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
- Assuming ASCII 128
思路
在時間復(fù)雜度最優(yōu)的情況下嗽交，考慮構(gòu)成字符串的字母集，字母集比 hash 表要小得多颂斜，利用字母集取代 hash 表來達(dá)到優(yōu)化空間復(fù)雜度的目的
定義數(shù)組：- int[26] for Letters 'a' - 'z' or 'A' - 'Z'
- int[128] for ASCII
- int[256] for Extended ASCII
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
}
