前言：
作者：神的孩子在歌唱
大家好，我叫運智
3. 無重復字符的最長子串
難度中等6009收藏分享切換為英文接收動態反饋
給定一個字串 s ，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
示例 4:
輸入: s = ""
輸出: 0
提示：
0 <= s.length <= 5 * 104s由英文字母、數字、符號和空格組成
package 滑動視窗;
import java.util.HashSet;
import java.util.Set;
public class _3_無重復字符的最長子串 {
// 集合+滑動視窗原理+雙指標
public int lengthOfLongestSubstring(String s) {
// 通過右指標遍歷字符到集合中，如果集合發現重復字符就退出回圈,然后獲取之前的長度,
// 在通過左指標慢慢取出之前在集合中的數，直到沒有重復字符出現
// 定義左右指標left,right,和最大值ans
int ans=0,left=0,right=0;
// 定義集合
Set<Character> set=new HashSet<>();
// 第一層遍歷左指標,取出集合中的數
int len=s.length();
for(;left<len;left++) {
// 如果left不為0,說明要么right到頂，要么存在相同元素,如果是第二種就不斷移除
if (left!=0) {
// left左指標向左移動一格去除,因為之前++,left變成1,我們要移除第一個數,
// 若是下面遍歷還發現有相同元素，left=2，在移除第一個數
set.remove(s.charAt(left-1));
}
// 通過右指標,將元素遍歷到集合中,如果超過長度或者集合中已經存在該元素就停止
while(right<len&&!set.contains(s.charAt(right))) {
set.add(s.charAt(right));
// 不斷地移動右指標
right++;
}
if (right<len) {
ans=Math.max(ans, right-left);
}
// 通過比較每個視窗的長度來取最大值,視窗大小就是左指標減去右指標
ans=Math.max(ans, right-left);
}
return ans;
}
}
本人csdn博客：https://blog.csdn.net/weixin_46654114
轉載說明：跟我說明，務必注明來源，附帶本人博客連接，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300468.html
標籤：其他
上一篇：【測驗】軟體測驗之二八原則