Longest Substring Without Repeating Characters
LeetCode算法第3題
思路：
1榆俺、字符串或數(shù)組的子串問(wèn)題历葛，可以用兩個(gè)索引區(qū)間來(lái)表示。長(zhǎng)度即為：j - i + 1
2当纱、題目要求無(wú)重復(fù)呛每，時(shí)間復(fù)雜度低的查找可以想到哈希查找，通過(guò)使用HashSet來(lái)檢查字符是否重復(fù)的時(shí)間復(fù)雜度為O(1)
流程：
①創(chuàng)建一個(gè)HashSet來(lái)保存當(dāng)前字符串的字符
② i 和 j 兩個(gè)索引表示當(dāng)前子串坡氯，從0晨横、0開(kāi)始， i 和 j 表示的都是第一個(gè)字符
③把索引 j 逐個(gè)向右掃描箫柳，并檢查索引 j 位置的字符是否在set中
④如果索引 j 位置的字符不在set中手形，則將索引 j 位置的字符加入set
⑤查看并比較當(dāng)前子串長(zhǎng)度
⑥繼續(xù)將 j 索引向右
⑦如果索引 j 位置的字符在set中，則將索引 i 位置的字符移出set
⑧并將索引 i 向右移動(dòng)（如果索引 j 位置的字符仍然在set中悯恍，則繼續(xù)執(zhí)行⑦⑧）
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();//<1>
int ans = 0, i = 0, j = 0;//<2>
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {//<3>
set.add(s.charAt(j));//<4>
ans = Math.max(ans, j - i + 1);//<5>
j++;//<6>
} else {
set.remove(s.charAt(i));//<7>
i++;//<8>
}
}
return ans;
}
}
時(shí)間復(fù)雜度库糠，最多進(jìn)行兩個(gè)循環(huán)，把i循環(huán)到n涮毫，把j循環(huán)到n曼玩，所以為O(2n)鳞骤，即為O(n)
空間復(fù)雜度取決于要查找的字符，set要能裝下所有不同的字符
