一、解题方法:滑动窗口
1.本题可以使用双层for循环暴力破解,但是时间复杂度很高,会达到O(n^2),所以采用滑动窗口的方法来降低时间复杂度。
2.定义一个HashMap数据集合,其中key值为字符,value值为字符位置+1,+1表示从字符位置后一个开始不重复
3.我们定义不重复子串的开始位置为start,结束位置为end
4.随着end不断遍历向后,会遇到与[start,end]区间内字符相同的情况,此时将字符作为key值,获取其value值,并更新start,此时[start,end]区间内不存在重复字符
5.无论是否更新start,都会更新其map数据集合和结果ans
6.最终的时间复杂度是O(N)
二、代码如下
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character,Integer> hashMap = new HashMap<>();
int ans = 0;
for(int start = 0,end = 0;end < s.length();end++)
{
char ch = s.charAt(end);
if(hashMap.containsKey(ch))
{
start = Math.max(hashMap.get(ch),start);
}
ans = Math.max(ans,end-start+1);
hashMap.put(ch,end+1);
}
return ans;
}
}