目錄
1.題目
2.題解
3.復雜度
1.題目
給定一個字串 s ，請你找出其中不含有重復字符的 最長子串 的長度，
題目來源：力扣（LeetCode）
2.題解
使用哈希來實作滑動視窗
在左指標向右移動的時候，我們從哈希集合中移除一個字符，在右指標向右移動的時候，我們往哈希集合中添加一個字符，
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) {
return 0;
}
// 哈希集合，記錄每個字符是否出現過
Set<Character> cur = new HashSet<Character>();
int n = s.length();
//右指標，初始值為 -1，相當于我們在字串的邊界的左側，還沒有開始移動
int rigth = -1;
//左指標
int left = 0;
for (int i = 0; i < n; i++) {
if (i != 0) {
//左指標向右移動一步，移除一個字符
cur.remove(s.charAt(i - 1));
}
while (rigth + 1 < n && !cur.contains(s.charAt(rigth +1))) {
//一直移動右指標
cur.add(s.charAt(rigth +1));
++rigth;
}
//第 i 到 right 個字符是一個極長的無重復字符子串
left = Math.max(left, rigth - i + 1);
}
return left;
}
}
3.復雜度
時間復雜度：O（n）
空間復雜度：O（n）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/404008.html
標籤：其他
上一篇：ggplot2可視化分面圖（faceting）使用label_wrap_gen函式設定每個分面圖的子圖示題自動換行為多行文本（基于設定的當行寬度進行標題文本自動換行）