当前位置：网站首页>无重复字符的最长子串

无重复字符的最长子串

2022-08-09 10:51:00 【ase2014】

题目

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

题解

使用滑动窗口实现
实际就为操作左右两个index left, right，right一直增加，left为当right出现重复的时候，left调为之前老的index+1
而且old index必须大于等于left index（即存在的必须在left ~ right之间）

代码

func lengthOfLongestSubstring(s string) int {
	sLen := len(s)
	if sLen < 2 {
		return sLen
	}

	result := 0
	l, r := 0, 0
	flag := make(map[int32]int, sLen)
	for i, v := range s {
		o, ok := flag[v]
		// 存在的字母的index必须在[l, r]内
		if ok && o >= l {
		    // 将l设置为o + 1，即存在的字母的下一个
			l = o + 1
		}
		flag[v] = i
		r += 1
		tmp := r - l
		if result < tmp {
			result = tmp
		}
	}
	return result
}

原网站

版权声明
本文为[ase2014]所创，转载请带上原文链接，感谢
https://blog.csdn.net/u014763610/article/details/118143951