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 滑动窗口方法总结