Fork me on GitHub

Lonest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map=new HashMap<>();
int leftBound=0,max=0;
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
leftBound=Math.max(leftBound,map.containsKey(c)?map.get(c)+1:0);
max=Math.max(max,i-leftBound+1);
map.put(c,i);
}
return max;
}
}

思路:
采取滑动窗口的方式,”窗口”向右滑动,每当加到一个新char的时候,左边检查有无重复的char,然后如果没有重复的就正常添加,有重复的话就左边扔掉一部分(从最左到重复char这段扔掉),在这个过程中记录最大窗口长度

钱聪 wechat
欢迎交流学习。
么么!