问题描述
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3
Explanation: 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.
解决思路
用两个指针i和j,分别用来记录存储和记录删除。如果HashSet里面不存在j指向的字符，就存进去，同时每次更新最大长度。如果存在，则开始移动i指针，依次删除set里面的元素，直到删除掉和j指针指向的相同的元素为止。此时再将j指针指向的元素放进set，重复以上。
代码
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
int res = 0;
//use two pointers to add and remove charaters
int i = 0;
int j = 0;
Set<Character> set = new HashSet<>();
while(i < len && j < len){
//add character into HashSet if it did not exist
if(!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
res = Math.max(res, j - i);
}else{//remove charaters in s until no same charater exists
set.remove(s.charAt(i++));
}
}
return res;
}
}
效率探究
时间复杂度：O(n)
空间复杂度：O(n)
小感想
首先，这一类型需要前后比较的，要想到需要设置前后两个pointer比较；第二，遇到重复类型的题，可以考虑使用HashSet处理，因为HashSet里面的值，有不可重复性。
