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.
在用Java 解答时 有用hashMap 和hashSet 两种解法
hashSet
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)
{
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;
}
}
思路较为简单，如果里面已经有该值了，就移除前面的，直到没有重复
hashMap
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;
}
}
如果键相同 值会把后面的值给覆盖，思路就是如果Map 中已经有该值，就找到上一个重复的，并且与当前的i比较，取da
