LeetCode3☞无重复字符的最长子串

关联LeetCode题号3

本题特点

• 滑动窗口，哈希，队列

本题思路

1. 最初想法“统计最长的无重复子串”，必然有逻辑：一旦出现重复子串，之前统计的长度即为无效长度，应该重新统计，即将无效的长度范围内的元素丢弃，重新开始统计
2. 基于以上想法，决定使用滑动窗口，使用栈为窗口，统计栈中留下的有效子串和之前统计的长度作比较，一旦有重复的则出栈，重新统计长度。
3. 即 实现窗口滑动是让不符合要求的元素出栈，这样编写会比较麻烦，容易漏掉一些情况
4. 优化之后的想法：字典作为窗口，使用left，right不断变化来实现滑动，代码简洁

Python写法一

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:if len(s) == 0:return 0maxLength = 1que = []que.append(s[0])for i in range(1, len(s)):if s[i] in que:maxLength = max(maxLength, len(que))while que[0] != s[i]:que.pop(0)que.pop(0)que.append(s[i])if maxLength < len(que):maxLength = len(que)return maxLength

Python优化写法

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 字典作为窗口hashmap = {}# left right 之间为符合要求的子串 两者变动实现滑动窗口left = 0res = 0for right in range(len(s)):hashmap[s[right]] = hashmap.get(s[right], 0) + 1while hashmap[s[right]] > 1:hashmap[s[left]] = hashmap.get(s[left]) - 1left += 1# right表示当前索引  left表示下一次索引 所以需要加1res = max(res, right-left+1)right += 1return res 

Java写法

class Solution {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> window = new HashMap<>();int left = 0, right = 0;int res = 0;while (right < s.length()){char c = s.charAt(right);right ++;window.put(c, window.getOrDefault(c, 0)+1);while (window.get(c) > 1){char d = s.charAt(left);left ++;window.put(d, window.get(d) - 1);}// right 和left 都是表示的下一次的索引 所以不需要加1res = Math.max(res, right - left);}return res;}
}