题解 | #最长不含重复字符的子字符串#

最长不含重复字符的子字符串

https://www.nowcoder.com/practice/48d2ff79b8564c40a50fa79f9d5fa9c7

package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param s string字符串
 * @return int整型
 */
// 思路:
// 既然要找一段连续子串的内不重复的长度,可以使用滑动窗口,保证窗口内都是不重复的
// 然后窗口右界不断向右滑,如果窗口内出现了重复字符,说明新加入的元素与之前的重复了,只需要窗口左界也向右收缩就可以保证窗口内都是不重复的
// 而保证窗口内的元素不重复,可以使用根据 key 值快速访问的哈希表,key 值为窗口内的元素,value 为其出现次数,只要新加入窗口的元素出现次数不为 1,就是重复
func lengthOfLongestSubstring(s string) int {
	// write code here
	// 用于统计字符元素出现的次数
	wc := make(map[byte]int)
	var ret int
	// 窗口左右界都从字符串首部开始,每次窗口优先右移右界,并统计进入窗口的元素的出现频率
	for l, r := 0, 0; r < len(s); r++ {
		wc[s[r]]++

		// 一旦右界元素出现频率大于 1,就需要右移左界直到窗口内不再重复
		for wc[s[r]] > 1 {
			// 将左边的元素移除窗口的时候同时需要将它在哈希表中的频率减 1,保证哈希表中的频率都是窗口内的频率
			wc[s[l]]--
			l++
		}

		// 每轮循环,维护窗口长度最大值
		ret = max(ret, r-l+1)
	}

	return ret
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务