題目描述
給定一個字符串构订，請你找出其中不含有重復字符的最長子串的長度
數據結構
- 數組齐饮、指針、哈希表
算法思維
- 雙指針胸墙、哈希（散列）
解題要點
- “范圍問題” 或 “同步變化” ==> 雙指針
- “快速查找” 或 “重復匹配” ==> 哈希表
關鍵知識點：哈希表 與 哈希算法
Hash table：哈希表，也叫散列表
? 把關鍵碼值映射到表中的一個位置按咒，以加快查找速度
Hash 算法
? 散列值：把任意長度的輸入通過算法變成固定長度的輸出
? 是一種壓縮映射迟隅，直接取余操作
? 哈希沖突的解決：開放尋址；再散列励七；鏈地址法智袭；
位運算
? & | ~ ^ << >> >>>
? 取模操作： a % (Math.pow(2,n)) ? 33 % 16 = 1
? 等價于：a & (Math.pow(2,n)-1) ? 33 & 15 = 1
解題步驟
一. Comprehend 理解題意
1. 題目主干要求
- 返回最長子串的長度
- 子串中無重復字符
- 子串，而非子序列："wke"是子串掠抬，"pwke"是子序列
2. 其它細節(jié)
- 測試數據僅包含 ASCII 碼表中的字符
- 字符串可能為空吼野，或全部由空字符組成
解法一：暴力解法
- 先找到所有不重復子串，再統(tǒng)計最長子串的長度
- 查找子串時两波，只保留不含重復字符的串
- 需要將這些子串臨時存儲在一個容器中
- 使用語言特性（Java）
解法二：優(yōu)化解法
- 在原字符串上定位并計算子串長度瞳步，取最大值
- 查找不含重復字符的子串，通過索引計算其長度
- 每次計算與上次子串長度對比腰奋，只保留最大的數值
二. Choose 選擇數據結構與算法
解法一：統(tǒng)計最長子串的長度
- 數據結構：數組/棧/鏈表/隊列+字符串
- 算法思維：遍歷+雙指針（外層循環(huán)start单起，內層循環(huán)end）
解法二：計算并保留最大子串長度
- 數據結構：字符串（臨時子串）
- 算法思維：遍歷+雙指針
三. Code 編碼實現(xiàn)基本解法
解法一：暴力解法思路分析
- 生成所有不包含重復字符的子串
將所有單字符子串添加到集合（ArrayList）中
遍歷字符串，外層循環(huán)為 start劣坊，內層為 end
截取不含重復字符的子串嘀倒，添加到集合中 - 統(tǒng)計最長子串的長度
遍歷集合，統(tǒng)計最大子串長度并返回
邊界問題
- 遍歷字符串的字符，注意索引越界
- 生成子串時，注意子串的起止索引
細節(jié)問題
- 子串添加到 ArrayList斗塘，它會動態(tài)擴容
class Solution {
public int lengthOfLongestSubstring(String s) {
int length;
if(s == null || (length = s.length()) == 0) return 0;
// 1.生成所有不包含重復字符的子串
List < String > list = new ArrayList < > ();
list.addAll(Arrays.asList(s.split(""))); // 單字符贱纠，直接添加到集合中
for(int start = 0; start < length; start++) { // 遍歷子串的起始字符
for(int end = start + 1; end < length; end++) { // 遍歷子串的終止字符
String subStr = s.substring(start, end);
// 當前字符在前面的子串中已出現(xiàn)，則跳過該字符
if(subStr.indexOf(s.charAt(end)) != -1) {
break;
}
list.add(s.substring(start, end + 1)); // 否則，添加到集合中
}
}
// 2.統(tǒng)計最長子串的長度
int maxLength = 1;
for(String sub: list) {
int subLen;
if((subLen = sub.length()) > maxLength) maxLength = subLen;
}
return maxLength;
}
}
時間復雜度：O(n3)
? ? 將字符串切割成單字符數組：O(n)
? ? 遍歷并截取子串：O(n3)
? ? 統(tǒng)計最長子串長度：O(n2)
? ? 實際時間消耗巨大
空間復雜度：O(n2)
? ? 數組列表：O(n2)，理論上最多有 n(n + 1) / 2 個子串
? ? 子串都是常量：O(n2)
? ? 子串都是字符串常量，實際空間消耗巨大
執(zhí)行耗時：270 ms固逗，擊敗了 6.86% 的Java用戶
內存消耗：39.8 MB浅蚪，擊敗了 5.04% 的Java用戶
解法二：優(yōu)化解法解法思路分析
- 定義變量 maxLength 表示最大長度
- 使用雙指針截取不含重復字符的子串
- 計算子串長度，保留較大值到 maxLength
class Solution {
public int lengthOfLongestSubstring(String s) {
int len;
if(s == null || (len = s.length()) == 0) {
return 0;
}
int maxLength = 1; // 最長子串的長度烫罩。默認值1：原字符串有數據惜傲，至少是1
// 1.遍歷字符串，生成所有的不含重復字符的子串
for(int start = 0; start < len; start++) { // 遍歷子串的起始字符
for(int end = start + 1; end < len; end++) { // 遍歷子串的終止字符
String subStr = s.substring(start, end); // 截取當前字符的前置子串
// 當前字符在前面的子串中已出現(xiàn)贝攒，則跳過該字符
if(subStr.indexOf(s.charAt(end)) != -1) {
break;
}
// 2.統(tǒng)計最長子串的長度
int subLen = end + 1 - start; // 子串長度
if(subLen > maxLength) maxLength = subLen;
}
}
return maxLength;
}
}
時間復雜度：O(n3)
? ? 將字符串切割成單字符數組：O(n)
? ? 遍歷并截取子串：O(n3)
? ? 統(tǒng)計最長子串長度：O(n2)
? ? 實際時間消耗巨大
空間復雜度：O(n2)
? ? 數組列表：O(n2)盗誊，理論上最多有 n(n + 1) / 2 個子串
? ? 子串都是常量：O(n2)
? ? 子串都是字符串常量，實際空間消耗巨大
執(zhí)行耗時：260 ms隘弊，擊敗了 7.06% 的Java用戶
內存消耗：39.4 MB哈踱，擊敗了 6.54% 的Java用戶
四. Consider 思考更優(yōu)解
剔除無效代碼或優(yōu)化空間消耗
- 能否不存儲子串？
- 能否避免生成字符串常量梨熙？
尋找更好的算法思維
- 能否只掃描一遍字符串开镣？
- 定位子串并檢查重復字符的過程比較耗時，能否優(yōu)化咽扇？
- 參考其它算法
五. Code 編碼實現(xiàn)最優(yōu)解
最優(yōu)解：哈希表 + 雙指針 解法
- 定義哈希表邪财，臨時存儲子串字符和查重
定義哈希函數，對任意字符生成唯一整數值 - 遍歷字符串质欲，通過雙指針循環(huán)定位子串
重復檢查右指針元素是否存在與哈希表中树埠；
? 是，刪除哈希表中左指針元素嘶伟，移動左指針
? 否怎憋，記錄到哈希表，計算長度奋早，移動右指針 - 每次計算子串長度盛霎，比較并保留最大值
邊界問題
- 遍歷字符串的字符赠橙，注意索引越界
- 計算子串長度時耽装，注意子串的起止索引
- 根據測試用例，子串長度不會超過哈希表容量：new char[128]
細節(jié)問題
- 子串長度是：end + 1 - start
- 出現(xiàn)重復元素后期揪，左指針逐個移動掉奄，直到與當前重復的字符索引+1
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0, left = 0, right = 0, len = s.length();
// 1.定義哈希表，支持ASCII碼表的全部字符
char[] chs = new char[128];
// 2.遍歷字符串的所有字符
while(right < len) { // 右指針后移凤薛，不超過源字符串長度
char rightChar = s.charAt(right); // 右指針字符
char c = chs[(chs.length - 1) & hash(rightChar)]; // hash算法計算索引
if(rightChar != c) { // 未重復出現(xiàn)
// 2.1.記錄到哈希表姓建，移動右指針，計算長度
char v = s.charAt(right++);
// 將不重復字符記錄到哈希表中
chs[(chs.length - 1) & hash(v)] = v;
// 3.每次記錄子串長度缤苫，并計算最大值
int size = right - left; // 每個不重復子串的長度
res = res > size ? res : size; // 取較大值
}
else { // 重復出現(xiàn)
// 2.2.刪除左指針元素速兔，移動左指針。重復檢查右指針元素是否還存在
char leftChar = s.charAt(left++);
chs[(chs.length - 1) & hash(leftChar)] = '\u0000';
}
}
return res;
}
}
時間復雜度：O(n) -- 遍歷字符串 O(n)活玲，定位重復字符 O(1)
空間復雜度：O(1) -- 哈希表占用固定空間 O(1)涣狗，雙指針 O(1)
執(zhí)行耗時：4 ms谍婉，擊敗了 90.12% 的Java用戶
內存消耗：38.8 MB，擊敗了 84.17% 的Java用戶
思路再優(yōu)化
- 哈希表作用變形
字符ASCII碼值 --> 字符
字符ASCII碼值 --> 字符最后出現(xiàn)索引 - 遇到重復元素后镀钓，左指針移動優(yōu)化
逐個移動到前一個相同字符出現(xiàn)后的位置 --> 一次性定位到前一個相同字符出現(xiàn)后的位置
再優(yōu)化解法
- 初始化哈希表穗熬，存入非 ASCII 碼值作為默認值
- 遍歷字符串，使用雙指針定位子串索引
字符已出現(xiàn)：取出哈希表中記錄丁溅，左指針到記錄+1
無論是否出現(xiàn)唤蔗，將右指針記錄到哈希表 - 每次移動都記錄子串長度，保留最大值
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0, // 最長子串的計算結果
left = 0, // 子串起始索引
right = 0, // 子串結束索引
len = s.length(); // 字符串長度
// 1.哈希表中填充ASCII碼表不包含的數值作為默認值：-1
int[] arr = new int[128];
for(int i = 0; i < arr.length; i++) arr[i] = -1;
// 2.遍歷字符串的所有字符
while(right < len) {
int c = s.charAt(right);
if(arr[c] != -1) { // 檢測該字符是否已出現(xiàn)：已出現(xiàn)
// 出現(xiàn)窟赏，則移動左指針妓柜，直接定位到上次出現(xiàn)的下一個索引
int start0 = arr[c] + 1;
// 2.1.使用雙指針定位子串索引：左指針直接定位
left = left >= start0 ? left : start0; // 只往右不往左
}
arr[c] = right; // 無論是否重復，記錄該字符最后一次出現(xiàn)的索引
// 3.計算子串長度饰序，記錄最大值：右索引+1 - 左索引
int size = right + 1 - left;
res = res > size ? res : size;
// 2.2.使用雙指針定位子串索引：右指針始終自增
right++;
}
return res;
}
}
時間復雜度：O(n) -- 遍歷字符串 O(n)领虹，定位重復字符 O(1)
空間復雜度：O(1) -- 哈希表占用固定空間 O(1) ，雙指針 O(1)
執(zhí)行耗時：2 ms求豫，擊敗了 100% 的Java用戶
內存消耗：38.7 MB塌衰，擊敗了 96.69% 的Java用戶
自實現(xiàn)代碼：
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = 0; //字符串長度
int subLen = 0; //子串長度
//0.非空判斷
if (s == null || (len = s.length()) == 0) return 0;
//1.定義哈希表，臨時存儲子串字符和查重
char[] hashtable = new char[128];
char[] arr = s.toCharArray();
int left = 0;
int right = 0;
//2.遍歷字符串蝠嘉，通過雙指針循環(huán)定位子串
while (left < len) {
//判斷右指針在哈希表中是否存在
if (hashtable[hash(arr[right])] == '\u0000') {
//不存在最疆，記錄到哈希表，計算長度蚤告，移動右指針
hashtable[hash(arr[right])] = arr[right];
//3.每次計算子串長度努酸，比較并保留最大值
if (subLen < (right - left + 1)) {
subLen = right - left + 1;
}
if (right < len - 1) {
right++;
}
} else {
//重復檢查右指針元素是否還存在
while (hashtable[hash(arr[right])] != '\u0000') {
//若存在，刪除哈希表中左指針元素杜恰，移動左指針
hashtable[hash(arr[left])] = '\u0000';
left++;
}
}
}
return subLen;
}
//定義哈希函數获诈，對任意字符生成唯一整數值
private int hash(char c) {
return c;
}
}
執(zhí)行耗時：3 ms，擊敗了 95.16% 的Java用戶
內存消耗：38.3 MB心褐，擊敗了 93.04% 的Java用戶
六. Change 變形與延伸
題目變形
- （練習）使用Set集合改進暴力解法
- （練習）使用Map集合實現(xiàn)哈希表解法
延伸擴展
- 合理的使用雙指針能將時間復雜度從 O(n2) 降低到 O(n) 級別
- 哈希表應用廣泛舔涎，是非常重要的數據結構（比如 HashMap）
