当前位置 博文首页 > Olivia_he:【LeetCode系列】 无重复字符的最长子串 Longest Sub
题目描述(Middle):
官方解答:https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
一个一个地检查子串看是否有重复字符
算法描述:
假设有一个函数? boolean allUnique(String substring)? ,当子串的字符无重复时返回true,否则返回false。我们可以通过对给定字符串? s? 的所有可能子串都调用该? allUnique? 函数。如果返回为true(说明无重复),则更新无重复的最长子串的长度。
具体如下:
代码如下:
public class Solution{
public int lengthOfLongestSubString(String s){
int n = s.length(), ans = 0;
for(int i = 0; i < n; i++){ //循环遍历子串看子串中的字符是否重复
for(int j = i + 1; j <= n; j++){
if(allUnique(s, i, j))
ans = Math.max(ans, j - i) //若不重复则更新不重复最长子串的长度
}
}
return ans
}
//判断字符串是否全是单一的函数,是返回True,否则返回False
public boolean allUnique(String s, int start, int end){
Set<Character> set = new HashSet<>(); //集合set存储字符
for(int i = start; i < end; i++){ //从开头位置遍历到结尾位置
Character ch = s.charAt(i); //获取i位置的字符
if(set.contains(ch)) //判断字符是否在集合set中
return false; //若在集合set中表示有重复,非单一
set.add(ch); //在集合中增加新字符
}
return true;
}
}
算法描述:
在上一方法中,我们一直重复地检查一个子串,看它是否有重复字符,但实际上是没有必要的。如果一个从索引 i 到 j - 1的子串??已经检查到没有重复字符了,那我们就只需要检查? 是否在??中就行了。
为了检查一个字符是否已经在这个子串中,我们可以循环扫描这个子串。但是复杂度为。我们可以用滑动窗口方法进行优化,将HashSet作为一个滑动窗口。
滑动窗口指的是在数组或字符串中某一范围的元素,比如:[i, j) 下标范围内的元素。如果我们将 [i, j) 向右移动一个元素则变成了 [i+1, j+1)。
我们用HashSet存储现有窗口 [i, j) 的字符(初始时 i = j)。然后我们将索引 j 向右滑动, 如果(指向的新的字符)不在HashSet中则继续向右滑动,直到 s[j] 已经在HashSet中为止。当然,无重复字符的最长子串是从索引 i 开始的。对所有的 i 进行此操作就可以得到答案。
代码如下:
public class Solution{
public int lengthOfLongestSubString(String s){
int n = s.length(), ans = 0;
Set<Character> set = new HashSet<>();
int i = 0, j = 0;
while(i < n && j < n){
if(!set.contains(s.charAt(j))){ //若集合set中不包含索引j的字符
set.add(s.charAt(j++)); //将该字符存入集合set中,j++窗口右移
and = Math.max(ans, j - i); //更新结果
}
else{ //若集合set中包含索引j的字符
set.remove(s.charAt(i++)); //将索引i的字符移出集合set,i++继续循环判断
}
}
return ans;
}
}
在方法二中可以很明显看到弊端,即当遇到有 j 指向的字符存在集合中时需要一点一点移动 i 。实际上假设 s[j] 在 [i, j) 窗口范围内有重复的字符且其索引为 j' ,我们可以跳过 [i, j'] 范围内的所有元素,直接置 i 为 j' + 1 。
因此可以用HashMap将每个字符和其所在位置一一对应起来。
代码如下:
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0, n = s.length();
Map<Character, Integer> map = new HashMap<>(); //HashMap存储(不重复的)字符和字符下标対
for(int i = 0, j = 0; j < n; j ++){
if(map.containsKey(s.charAt(j))){ //若新的字符已经在HashMap中
i = Math.max(map.get(s.charAt(j)), i); //将窗口的左端i移动到该字符的最大值下标
}
ans = Math.max(ans, j - i + 1); //计算窗口大小
map.put(s.charAt(j), j + 1); //将新的字符放入HashMap中
}
return ans;
}
}
上述算法都没有对字符串? s? 使用的字符集进行 假设。我们知道字符集是很小的,我们可以将 Map 换为整形数组来直接访问。
如 index[65] 表示字符 'A' 的索引值。(注:在ASCII码表中 'A' 是 65)
常用表示如下:
可修改代码如下:
public class Solution{
public int lengthOfLongestSubstring(String s){
int n = s.length(), ans = 0;
int[] index = new index[128]; //当前字符的索引数组
for(int i = 0, j = 0; j < n; j++){
i = Math.max(index[s.charAt(j)], i); //找到j的字符索引和i的最大值,即如果有重复取i最大的那个
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1; //存储j的字符的索引为j+1
}
return ans;
}
}
?
cs