无重复数字的最长子串

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

func lengthOfLongestSubstring(s string) int {
    // 通过滑动窗口实现
    res := 0
    l := -1
    for r:=0;r < len(s);r++ {
        if l == -1 {
            l = r
        } else {
            for j := r-1;j >= l;j-- {
                if s[j] == s[r] {
                    l = j + 1
                    break
                } 
            }
        }
        if r - l + 1 > res {
            res = r - l + 1
        }
    }
    return res
}

解题思路

Ⅰ

利用s[left:i+1]来表示s[:i+1]中的包含s[i]的最长子字符串。 location[s[i]]是字符s[i]在s[:i+1]中倒数第二次出现的序列号。当left < location[s[i]]的时候，说明字符s[i]出现了两次。需要设置 left = location[s[i]] + 1, 保证字符s[i]只出现一次。

Ⅱ

核心：只增大不减小的滑动窗口
流程：两个指针start和end表示窗口大小，遍历一次字符串，窗口在遍历过程中滑动或增大
tips：配合画图思考更佳

窗口内没有重复字符：此时判断i+1与end的关系，超过表示遍历到窗口之外了，增大窗口大小
窗口内出现重复字符：此时两个指针都增大index+1，滑动窗口位置到重复字符的后一位
遍历结束，返回end-start，窗口大小
思考：如果需要返回字符串怎么做？
解答：只需要在窗口增大的时候记录start指针即可

题解

Ⅰ

unc lengthOfLongestSubstring(s string) int {
	// location[s[i]] == j 表示：
	// s中第i个字符串，上次出现在s的j位置，所以，在s[j+1:i]中没有s[i]
	// location[s[i]] == -1 表示： s[i] 在s中第一次出现
	location := [256]int{} // 只有256长是因为，假定输入的字符串只有ASCII字符
	for i := range location {
		location[i] = -1 // 先设置所有的字符都没有见过
	}

	maxLen, left := 0, 0

	for i := 0; i < len(s); i++ {
		// 说明s[i]已经在s[left:i+1]中重复了
		// 并且s[i]上次出现的位置在location[s[i]]
		if location[s[i]] >= left {
			left = location[s[i]] + 1 // 在s[left:i+1]中去除s[i]字符及其之前的部分
		} else if i+1-left > maxLen {
			// fmt.Println(s[left:i+1])
			maxLen = i + 1 - left
		}
		location[s[i]] = i
	}

	return maxLen
}

Ⅱ

func lengthOfLongestSubstring(s string) int {
    // 通过只增大不减小的滑动窗口实现
    start, end := 0, 0
	for i := 0; i < len(s); i++ {
		index := strings.Index(s[start:i], string(s[i]))
		if index == -1 {
			if i+1 > end {
				end = i + 1
			}
		} else {
			start += index + 1
			end += index + 1
		}
	}
	return end - start
}

总结

熟悉滑动窗口的用法