1.题目描述
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given =="abcabcbb"==, the answer is =="abc"==, which the length is 3.
Given =="bbbbb"==, the answer is =="b"==, with the length of 1.
Given =="pwwkew"==, the answer is =="wke"==, with the length of 3. Note that the answer must be a substring, =="pwke"== is a subsequence and not a substring.
2.我的分析思路
说实话，这题当时拿到没有什么思路，惭愧。。。
3.其他的思路
看了讨论之后，直接贴出代码吧，中间比较精妙。
方法1：
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
}
方法2：
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}
