問題描述
請從字串中找出一個最長的不包含重復字符的子字串，計算該最長子字串的長度，
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
提示：
s.length <= 40000
解題思路（雙指標）
我們不妨以示例1中的字串abcabcbb為例，找出從每一個字符開始的，不包含重復字符的最長子串，那么其中最長的那個字串即為答案，對于示例一中的字串，我們列舉出這些結果，其中括號中表示選中的字符以及最長的字串：
以第1個字符a開頭的不含重復字符的最長子串為(abc)abcbb
以第2個字符b開頭的不含重復字符的最長子串為a(bca)bcbb
以第3個字符c開頭的不含重復字符的最長子串為ab(cab)cbb
以第4個字符a開頭的不含重復字符的最長子串為abc(abc)bb
以第5個字符b開頭的不含重復字符的最長子串為abca(bc)bb
以第6個字符c開頭的不含重復字符的最長子串為abcab(cb)b
以第7個字符b開頭的不含重復字符的最長子串為abcabc(b)b
以第8個字符b開頭的不含重復字符的最長子串為abcabcb(b)
我們可以發現，如果我們依次遞增地列舉子串的起始位置，那么子串的結束位置也是遞增的！
由于這種隱式的遞增性，我們就可以使用雙指標演算法來解決
我們定義兩個指標i,j，其中指標i表示列舉每個子串的起始位置，而指標j表示不包含重復子串的結束位置，
而判斷子串是否包含重復元素我們可以借助Java中的set集合
在每一次回圈遍歷的程序中，我們會將指標i向后移動一格，相應的前面一個元素將在集合中被去除，緊接著判斷以i為起始位置，j+1為結束位置的子串中是否包含重復的字符，如果不包含，那么我們就把j所指向的元素添加到集合中，并讓j往后移動一位，一直遇到某個j+1使得子串中包含重復元素或者走到了字串的盡頭為止，在這程序中我們需要每次比較前面遍歷程序中所得到的最大長度值與本次遍歷程序中所得到的最大長度值，最終就可以得到最長不包含重復字符的子字串，
實作代碼
class Solution {
public int lengthOfLongestSubstring(String s) {
int result=0; //結果變數
int len=s.length();
Set<Character> sets=new HashSet<Character>(); //set集合用來判斷子字串是否包含重復元素
int j=-1; //j指標即結束位置指標初值應該為-1
for(int i=0;i<len;i++){
if(i!=0){ //每次遍歷新的起始位置，都要把前面的元素從集合中移出，
sets.remove(s.charAt(i-1));
}
//向后移動j指標，直到遇到字串結尾或者將要包含重復元素為止
while(j+1<len && !sets.contains(s.charAt(j+1))){
//當添加下一個元素，仍不包含重復元素時，可以添加進行，并把j指標后移
sets.add(s.charAt(j+1));
j++;
}
result=Math.max(result,j-i+1); //更新結果變數
}
return result;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/259462.html
標籤：java