class Solution {
/*
* 2018.01.16
* 解題方法:動态規劃,但是今天新學了一招:滑動視窗----有點猛
* 定義左右left、right指針,map數組,然後周遊判斷
*/
public int lengthOfLongestSubstring(String s) {
if(s == null || s.equals("")){
return 0;
}
int n = s.length();
int R = 256;
int[] map = new int[R];//桶:字元的個數的
int left = 0, right = 0;//視窗的兩個指針
int maxLen = Integer.MIN_VALUE;//最後的結果
//boolean notSameChar = true;
//現在漏掉了一種情況,就是周遊的結尾的時候都沒有遇到重複的(前面有可能有重複的判斷了)
//如:aeabcd,aea重複判斷了;但是在left指向1--e時,right從2變回到1,right++周遊到結尾d時都沒有遇到相同的,是以要人為判斷一下
while(right < n){
char current = s.charAt(right);
map[current]++;
if(map[current] > 1){//說明這裡有重複字元出現,然後rigth左移動一位
map[current]--;
int currentLen = right - left;
maxLen = maxLen > currentLen? maxLen : currentLen;
map[s.charAt(left)]--;
left++;
//notSameChar = false;
continue;
}
if(right == n - 1){
maxLen = right-left+1 < maxLen? maxLen : right-left+1;
}
right++;
}
return maxLen == Integer.MIN_VALUE? 0 : maxLen;
}
}
參考文獻:
leetcode:Find All Anagrams in a String 滑動視窗方法總結