无重复字符的最长子串:
题目:
题目:https://leetcode.cn/problems/longest-substring-without-repeating-characters/
题目大意:
在一个字符串重寻找没有重复字母的最长子串。
思路:
采用滑动窗口的思想进行解题,滑动窗口的右边界不断的右移,只要没有重复的字符,就持续向右扩大窗口边界;一旦窗口内出现了重复字符,就需要缩小左边界,直到重复的字符移出了左边界,然后继续移动滑动窗口的右边界。
注意点:
无论有无重复字符,右边界都会向右持续移动
重复字符出现在窗口内idx>=left,才需要进行滑动左边界,如果出现在窗口外,就不要滑动左边界。
题解:
// 滑动窗口 func lengthOfLongestSubstring(s string) int { right, left, res := 0, 0, 0 indexes := make(map[byte]int) for right < len(s) { if idx, ok := indexes[s[right]]; ok { // 这里需要注意,只有重复字符在窗口内部才需要滑动左边界 if idx >= left { left = idx + 1 } } // 没注册就注册,注册过就更新位置 indexes[s[right]] = right // 滑动右边界 right++ res = max(res, right-left) } return res } func max(a, b int) int { if a > b { return a } return b }