hello占调，大家好暂题，我是腿短快跑，今天的主題是算法究珊，這是我昨天刷的一道算法題薪者。歡迎大家一起溝通有沒有更好的實(shí)現(xiàn)方法
本文最先發(fā)布于我的個(gè)人博客，簡書為同步發(fā)布剿涮，如果有需要請?jiān)L問 腿短快跑的個(gè)人博客
題目描述
給定一個(gè)字符串 s 言津，請你找出其中不含有重復(fù)字符的最長子串的長度。
示例
輸入: s = "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"取试，所以其長度為 3悬槽。輸入: s = "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1瞬浓。輸入: s = "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"初婆，所以其長度為 3。
請注意，你的答案必須是 子串 的長度磅叛，"pwke" 是一個(gè)子序列屑咳，不是子串。
提示
- 0 <= s.length <= 5 * 10?
- s 由英文字母弊琴、數(shù)字兆龙、符號(hào)和空格組成
題解
滑動(dòng)窗口
思路
- 左右兩個(gè)指針表示滑動(dòng)窗口的左右邊界
- 在每一次判斷中，我們將左指針向右移動(dòng)一個(gè)敲董，表示從下一個(gè)元素開始判斷紫皇，同時(shí)右指針不斷的向后移動(dòng)，在此過程中需要保證左右指針中間的字符沒有重復(fù)臣缀，移動(dòng)結(jié)束后記錄左右指針之間的距離坝橡，判斷是否包含重復(fù)字符可以采用哈希表來判斷
- 將最長的左右指針之間的距離返回
實(shí)現(xiàn)
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() <= 0) {
return 0;
}
char[] chars = s.toCharArray();
Set<Character> hash = new HashSet<>();
int max = 0;
// i表示左指針，j表示右指針
for (int i = 0; i < chars.length; i++) {
hash.clear();
hash.add(chars[i]);
for (int j = i + 1; j < chars.length; j++) {
// 判斷是否存在
if (hash.contains(chars[j])) {
break;
} else {
hash.add(chars[j]);
}
}
if (max < hash.size()) {
max = hash.size();
}
}
return max;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：精置，因?yàn)槲覀兠看味际菑淖笾羔樜恢瞄_始循環(huán)计寇，最復(fù)雜的情況每次都需要遍歷到結(jié)尾
空間復(fù)雜度：，主要為數(shù)組和哈希表的開銷
性能
執(zhí)行耗時(shí):66 ms脂倦，擊敗了12.53% 的Java用戶
內(nèi)存消耗:41.9 MB番宁，擊敗了12.89% 的Java用戶
滑動(dòng)窗口優(yōu)化
思路
上述方法中，右指針每次都是從左指針的位置開始移動(dòng)赖阻，右指針存在大量的重復(fù)操作蝶押，我們可以從上一次的位置繼續(xù)向后移動(dòng)，只需要哈希表數(shù)據(jù)每次在左指針向后移動(dòng)的時(shí)候移除上一次的左指針的元素即可
實(shí)現(xiàn)
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合火欧，記錄每個(gè)字符是否出現(xiàn)過
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指針棋电，初始值為 -1，相當(dāng)于我們在字符串的左邊界的左側(cè)苇侵，還沒有開始移動(dòng)
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指針向右移動(dòng)一格赶盔，移除一個(gè)字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不斷地移動(dòng)右指針
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 個(gè)字符是一個(gè)極長的無重復(fù)字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
復(fù)雜度
時(shí)間復(fù)雜度：，左右指針各會(huì)將每個(gè)字符遍歷一遍
空間復(fù)雜度：榆浓，主要為哈希表的開銷
性能
執(zhí)行耗時(shí):5 ms于未，擊敗了60.30% 的Java用戶
內(nèi)存消耗:41.2 MB，擊敗了79.66% 的Java用戶
