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.
题目要求一个最长的无重复的子串（子串要求连续），我们可以想到使用set来操作，set可以保证内部元素全部是无重复的，这比我们使用暴力方法去遍历判断重复要优化很多。简单来说就是遍历一次字符串，用i和j来标记子串的开始和结束。每次遇到不同的就把元素加入到set中，同时子串长度+1,遇到相同的就从当前子串的开头开始删除，一直删除到重复元素的位置，比如说从i开始的第n个元素重复了，就删除掉从i到n的所有元素，这样新的不重复子串就是string[i+n+1,j+1]，再和旧的长度比较出最大的，如此重复直到字符串末尾。
由于很像网络流量控制的滑动窗口协议，所以这种方法也叫滑动窗口
class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length(),max=0;
int i=0,j=0;
HashSet<Character> set=new HashSet<Character>();
while(i<n&&j<n){
if(!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
max=Math.max(max,j-i);
}else{
set.remove(s.charAt(i++));
}
}
return max;
}
}
还可以从空间角度进行优化
当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map。
常用的表如下所示：
int [26] 用于字母 ‘a’ - ‘z’或 ‘A’ - ‘Z’
int [128] 用于ASCII码
int [256] 用于扩展ASCII码
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
}
python的话可以使用列表自带的切片来维护一个不重复集合set
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_number = 0
number = 0
test = ''
for i in s:
if i not in test:
test += i
number += 1
else:
if number >= max_number:
max_number = number
index = test.index(i)
test = test[(index+1):] + i
number = len(test)
if number > max_number:
max_number = number
return max_number