赞
赏
leetcode 官方第 3 题。给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
示例1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例4:
输入: s = ""
输出: 0
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成想要求最大子长串的长度,是需要将所有的字符遍历的。我们可以想象用一个容器,当容器里面没有这个字符的时候,就将字符往里面塞,如果容器里面有字符的时候,为了让容器里面的字符不重复,我们就需要将新插入的字符前面的所有字符都排出掉。如下:
我们可以看到前三步,由于没有重复的字符,所以我们可以将遍历到的字符放在容器里面,但是第四步,由于 a
已经在容器中存在,所以我们需要将存在的字符 a
及其左边的所有字符都移除出容器。后面的步骤类似。所以我们就可以拿到最大的长度为 3。
我们再以下面例子分析:
在第一步和第二步的时候,由于容器里面没有重复字符,所以可以往里面追加。第三步的时候,由于 w
已经存在,所以我们将容器中 w
字符之前的所有字符都移除,此事容器里面就只剩一个 w
。然后按照上面的流程依次往后执行,最终得到一个最大的长度值。
上面的两个步骤用到的主要思路叫做:滑动窗口。就是数据按照一定的顺序往桶里塞,比如数据从左往右慢慢变多,然后有重复了,就将左边的数据移除掉。
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) {
return 0;
}
//以字符为 key,索引为 value 存储,用来作为容器
Map<Character,Integer> containsMap = new HashMap();
//返回值
int retValue = 0;
//将字符串转换为字符数组
char[] strChars = s.toCharArray();
//最左边的字符索引,作用和移除数据一样,记录最左侧字符的位置
int leftIndex = 0;
for(int i=0;i<strChars.length;i++){
//判断已经遍历过的字符集是否包含当前字符
if(containsMap.keySet().contains(strChars[i])){
//获取被包含的字符的索引位置
int tmpIndex = containsMap.get(strChars[i]) ;
//最左边的位置比包含的索引位置小,将最左边的位置置换成包含位置的后一位
if(leftIndex <= tmpIndex){
leftIndex = containsMap.get(strChars[i]) + 1;
}
}
//获取当前位置和最左边字符的位置差
int currentSize = i - leftIndex + 1;
if(currentSize > retValue){
retValue = currentSize;
}
containsMap.put(strChars[i],i);
}
return retValue;
}
}
func lengthOfLongestSubstring(s string) int {
strLength := len([]rune(s))
if strLength == 0 {
return 0
}
//以字符为 key,索引为 value 存储,用来作为容器
containsMap := make(map[byte]int)
//返回值
retValue := 0
//将字符串转换为字符数组
strChars := []byte(s)
//最左边的字符索引,作用和移除数据一样,记录最左侧字符的位置
leftIndex := 0
for i := 0;i< strLength;i++ {
//判断已经遍历过的字符集是否包含当前字符
if _,isOk := containsMap[strChars[i]]; isOk {
//获取被包含的字符的索引位置
tmpIndex := containsMap[strChars[i]]
//最左边的位置比包含的索引位置小,将最左边的位置置换成包含位置的后一位
if leftIndex <= tmpIndex {
leftIndex = containsMap[strChars[i]] + 1
}
}
//获取当前位置和最左边字符的位置差
currentSize := i - leftIndex + 1
if currentSize > retValue {
retValue = currentSize
}
containsMap[strChars[i]] = i
}
return retValue
}