Question
难度：中等
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
Solution
这道题用
暴力穷举法我们不难想到但是面试，一定会问你，
还有别的方法吗？有，
滑动窗口法
假设有一个可滑动且大小可变的窗口，窗口左端（start）不动，右端（end）向后移动
当end遇到重复字符，start应该放在上一个重复字符的位置的后一位，同时记录最长的长度
怎样判断是否遇到重复字符，且怎么知道上一个重复字符的位置？
用哈希字典的key来判断是否重复，用value来记录该字符的下一个不重复的位置。
Code
class Solution { public int lengthOfLongestSubstring(String s) { int maxLength=0; int start = 0,end=0; HashMap<Character, Integer> map = new HashMap<>(); char[] chars = s.toCharArray(); while(end<chars.length){ if (map.containsKey(chars[end])){ start=Math.max(map.get(chars[end]),start); } maxLength=Math.max(maxLength,end-start+1); map.put(chars[end],end+1); end++; } return maxLength; } }
Result
复杂度分析
- 时间复杂度：O(N) ，只需要end从0移动到n就可以
🌈寻宝
⭐今天是坚持刷题更文的第3/100天
⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
⭐更多算法题欢迎关注专栏《leetcode》
为了回馈各位粉丝，礼尚往来，给大家准备了一条多年积累下来的优质资源，包括 学习视频、面试资料、珍藏电子书等
怎么领取请大家自己找，寻宝游戏现在开始。
找不到可以评论留言，一条就会注意到你。
如果还不行，请私信我。
