网络异常,图片无法展示
|
题目地址(3. 无重复字符的最长子串)
题目描述
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2: 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 示例 3: 输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。 示例 4: 输入: s = "" 输出: 0 提示: 0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成
思路
通过双指针和set检测是否有相同元素,有就左移set
代码
- 语言支持:Python3
Python3 Code:
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: left,right = 0,0 resMax = 0 hashSet = set() # 通过双指针和set检测是否有相同元素,有就左移set while right < len(s): while s[right] in hashSet: hashSet.remove(s[left]) left += 1 hashSet.add(s[right]) resMax = max(resMax, len(hashSet)) # print(hashSet) right += 1 return resMax
复杂度分析
令 n 为数组长度。
- 时间复杂度:O(n)O(n)
- 空间复杂度:O(n)O(n)