解法一:暴力枚举
- 先固定一个left,让right向右遍历
- 遇到重复的字符,让left加一
- 然后right返回,重新遍历
解法二: 滑动窗口(在解法一的基础上进行优化)
- 还是先固定一个left在起始位置,让right从起始位置开始向后遍历
- 每遍历一个字符的时候,将该字符放入哈希表中(进窗口)
- 当窗口内出现重复字符的时候,让left++,并且删掉left位置的值(出窗口),然后right继续向后走
- 最后出完窗口更新一下最大值
代码:
public int lengthOfLongestSubstring(String ss) {
//将字符串转换成字符数组
char[] s = ss.toCharArray();
int n = ss.length();
//因为是字符串的最长子串,所以可以用数组来模拟哈希表
int[] hash = new int[128];
//用数组下标来表示控制滑动窗口的指针
int left = 0;
int right = 0;
int ret = 0;
while(right < n){
//进窗口
hash[s[right]]++;
//判断
while(hash[s[right]] > 1){
//出窗口
hash[s[left++]]--;
}
//更新最大值
ret = Math.max(ret,right - left + 1);
right++;
}
return ret;
}