题目

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

示例 1:
**

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

示例 2:

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

示例 3:

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

方案一（双指针/滑动窗口+hashmap）

func lengthOfLongestSubstring(s string) int {
    var i, j int // i 在前
    m := map[rune]bool{}
    max_str_length := 0

    rune_s := []rune(s)
    for i < len(s) {
        if _, ok := m[rune_s[i]]; ok { // 存在
            delete(m, rune_s[j])
            if max_str_length < i - j {
                max_str_length = i - j
            }
            j += 1
        } else {
            m[rune_s[i]] = true
            i += 1
        }
    }
    if max_str_length < i - j {
        max_str_length = i - j
    }

    return max_str_length
}

• 上述方案可以优化，一次性跳过多个字符，而非目前这样一次跳过一个字符

方案二（leetcode）

func lengthOfLongestSubstring(s string) int {
    // 思路：
    // 使用 滑动窗口 遍历一遍
    // 使用 lastOccurred 记录每个字符最近出现的 index
    // 遍历的时候先看看是否在 lastOccurred 中存在
    // 如果存在更新 start 到最近 index + 1
    // 否则 start 不变
    // 更新或者不更新 start 之后比较 当前索引和 start 之间的长度与 maxLength 比较取最大
    // 更新当前 字符 在 lastOccurred 中的 索引

    var start int = 0
    var maxLength = 0
    lastOccurred := make(map[int32]int)

    //开始遍历 s
    for i, ch := range s {
        // 首先查找是否存在 lastOccurred
        lastI, exist := lastOccurred[ch]

        // 如果存在 并且 大于等于 start index
        // 注意，等于 start 也要更新，因为 start 包含在前子字符串
        if exist && lastI >= start {
            // 更新 start
            start = lastI + 1
        }
        // 不存在则不操作
        // 然后更新 maxLength
        if i - start + 1 > maxLength {
            maxLength = i - start + 1
        }
        // 更新当前字符 ch 在 lastoccurred 中的位置
        lastOccurred[ch] = i
    } 
    return maxLength
}

• 以上答案为 leetcode 答案

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetcod/

原文

https://leetcode-cn.com/explore/learn/card/hash-table/207/conclusion/826/