题解 | #最长不含重复字符的子字符串#
最长不含重复字符的子字符串
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 }