当前位置 博文首页 > 霖墨的博客：LeetCode第三题：无重复字符的最长子串（Longest Su
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
这题我第一次想到的是暴力破解，即3个循环,类似于字符串匹配
public int lengthOfLongestSubstring(String s){
int res = 0;
for(int i = 0;i<s.length();++i){
for(int j = i;j<s.length();++j){
if(isDifference(s,i,j)){//如果[i,j]之间的字符都不同
res = Math.max(j-i+1,res);//找到最长的字符串
}
}
}
return res;
}
/**
* function: 判断[start,end]之间的字符串是否都不同
* @param s -字符串
* @param start -起始下标
* @param end -结束下标
* @return
*/
public boolean isDifference(String s, int start, int end){
Set<Character> set = new HashSet<>();
for(int i=start;i<=end;++i){
if(set.contains(s.charAt(i)))
return false;
set.add(s.charAt(i));
}
return true;
}
这个我也不知道为什么叫滑动窗口（官方说的）。这个算法很简单，就是把所以的不同字符存到HashSet中。如果遇到HashSet里已经存在的字符，就把HashSet里的字符一个一个的移除，直到移除了重复的字符；如果HashSet里不存在这个字，就添加到HashSet里。
public int lengthOfLongestSubstring(String s){
int res = 0;
Set<Character> set = new HashSet<Character>();
for(int i= 0,j=0;i<s.length();){
if(!set.contains(s.charAt(i))){//字符不在HashSet里
set.add(s.charAt(i++));//添加字符
}else{
set.remove(s.charAt(j++));//移除字符
}
res = Math.max(res,set.size());//找到最长的字符串
}
return res;
}
我们以上的代码存在明显可优化的地方——当字符已经存在HashSet里时，不用一个一个地移除字符，而是一下子全部移除。在这里我们使用HashMap来保存字符和对应的下标(类似于KMP字符串匹配算法)。
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int res = 0;
for (int i = 0, j = 0; i < s.length();++i) {
if (map.containsKey(s.charAt(i))) {
j = Math.max(map.get(s.charAt(i)) + 1, j); //跳过重复的字符串
}
res = Math.max(res, i - j + 1);
map.put(s.charAt(i), i);
}
return res;
}
