题目 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
1 2 3 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
1 2 3 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
1 2 3 4 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成
简介 1 2 3 4 5 巧妙的使用 HashMap<Char, Int> 记录每个字符的最新的位置 巧妙的确定了每个元素对应的滑动窗口的左边界 关键词: HashMap <Char, Int>用以查找位置 窗口长度不固定,遍历指针作为左边界
正文 本题的巧妙在于使用 HashMap 和 遍历指针构建了一个滑动窗口
在寻找滑动窗口的时候,我们总是固定住一端位置去寻找另一端的位置,通常需要我们找到两个端点之间的关系
来分析滑动窗口的性质:左边届位置,右边界的位置,滑动窗口的长度 三者有以下这些关系:滑动窗口的长度 = 滑动窗口右边届 - 滑动窗口左边界 无论算法如何变化,我们知二求一
我们分析,遍历指针和左右边界的关系有三 情况一:遍历指针是滑动窗口的左边界 情况二:遍历指针是滑动窗口的右边界 情况三:遍历指针在滑动窗口的中间
结合滑动窗口的性质 情况一:知道窗口的长度,以遍历指针为左边界 情况二:窗口长度不固定,新增的元素决定窗口的长度,也就是左边界的位置 情况三:对于滑动窗口算法,通常情况下遍历指针要么位于窗口的左边界,要么位于右边界,用于控制窗口的扩展和收缩。在常规的滑动窗口算法中,遍历指针并不位于窗口的中间位置。
显然这种是情况二
当滑动窗口的位置和长度变化受制于新增的元素时,我们将遍历指针设置为
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { fun lengthOfLongestSubstring (s: String ) : Int { var maxLen = 0 var left = 0 val map = HashMap<Char , Int >() for (right in s.indices){ val char = s[right] if (map.containsKey(char) && map[char]!! >= left){ left = (map[char]?: 0 ) + 1 } map[char] = right maxLen = maxOf(maxLen, right - left + 1 ) } return maxLen } }