转载

无重复字符的最长子串

这道题难度中等：

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

解题思路：

设置start标志位和index标志位，index从前往后依次遍历
每次出现的字母，都缓存其最后一次出现的索引
如果index指向的字母的lastLndex在start前面，也就是小于start
如果当前字母的的lastIndex大于或者等于start，则start标志位移动到index的前面一位
每次遍历都更新lastIndex和maxLength

这题就很正常，go的实现无论是内存还是速度，都远块于java。

java实现：

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndex = new HashMap<>(s.length());
    int start =0, maxLength = 0, length = 0;
    for (int i =0; i < s.length(); i++) {
        Character ch = s.charAt(i);
        Integer lastIndex = charIndex.get(ch);
        if (Objects.nonNull(lastIndex) && charIndex.get(ch) >= start) {
            start = lastIndex + 1;
            length = i - start + 1;
        } else {
            length += 1;
        }
        maxLength = length > maxLength ? length : maxLength;
        charIndex.put(ch, i);
    }
    return maxLength;
}

golang实现：

func lengthOfLongestSubstring(s string) int {
    charIndex := make(map[rune]int)
    start, maxLength, length := 0, 0, 0
    for i, v := range []rune(s) {
        if lastIndex, ok := charIndex[v]; ok && lastIndex >= start {
            start = lastIndex + 1
            length = i - start + 1
        } else {
            length += 1
        }
        charIndex[v] = i
        if length > maxLength {
            maxLength = length
        }
    }
    return maxLength
}

来源：力扣（LeetCode）

链接： https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

原文 https://studygolang.com/articles/21234

正文到此结束