嗨客网搜索
无重复字符的最长子串

描述

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 由英文字母、数字、符号和空格组成

思路

想要求最大子长串的长度,是需要将所有的字符遍历的。我们可以想象用一个容器,当容器里面没有这个字符的时候,就将字符往里面塞,如果容器里面有字符的时候,为了让容器里面的字符不重复,我们就需要将新插入的字符前面的所有字符都排出掉。如下:

09_无重复字符最长子串.png

我们可以看到前三步,由于没有重复的字符,所以我们可以将遍历到的字符放在容器里面,但是第四步,由于 a 已经在容器中存在,所以我们需要将存在的字符 a 及其左边的所有字符都移除出容器。后面的步骤类似。所以我们就可以拿到最大的长度为 3。

我们再以下面例子分析:

10_无重复字符的最长子串分析.png

在第一步和第二步的时候,由于容器里面没有重复字符,所以可以往里面追加。第三步的时候,由于 w 已经存在,所以我们将容器中 w 字符之前的所有字符都移除,此事容器里面就只剩一个 w。然后按照上面的流程依次往后执行,最终得到一个最大的长度值。

上面的两个步骤用到的主要思路叫做:滑动窗口。就是数据按照一定的顺序往桶里塞,比如数据从左往右慢慢变多,然后有重复了,就将左边的数据移除掉。

代码具体实现

Java语言版本

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; } }

Go语言版本

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 }
嗨客网顶部