一、leetcode3. 无重复字符的最长子串★★
链给定一个字符串 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 由英文字母、数字、符号和空格组成
滑动窗口的使用：
模糊定义：计算结果，出现次数，同时包含，最长/最短，子串/子数组/子序列
用到双指针和哈希表，
HashSet 内不允许有相同的值出现，HashMap中不允许有相同的件出现，使用put()方法将元素放入map中 使用add()方法将元素放入set中
下面这个方法弊端：当出现重复元素时候，左指针到重复元素之间的元素都访问了两遍，时间复杂度太大
class Solution{ public int lengthOfLongestSubstring(String s) { //创建两个指针，初始位置都位于0处 int left = 0, right = 0; //用来记录最优解，并且实时更新 int bestresult = 0; //借助Hash来排除相同的数 HashSet<Character> character = new HashSet<>(); while (right < s.length() && left < s.length()) { //若窗口内没有相同的值，则右指针继续向右移动 if (!character.contains(s.charAt(right))) { character.add(s.charAt(right)); right++; //实时更新最优解的值 bestresult = Math.max(right - left, bestresult); } else { //如果有重复值出现，则将左指针右移，缩小窗口，缩小至范围内没有重复元素 character.remove(s.charAt(left)); left++; } } return bestresult; } }
借鉴大佬的代码后，进行代码优化： 优化后时间复杂度简便许多
class Solution{ public int lengthOfLongestSubstring(String s) { int bestresult = 0; Map<Character,Integer> character = new HashMap<>(); for(int right =0,left = 0;right <s.length();right++){ if (character.containsKey(s.charAt(right))) { left = Math.max(character.get(s.charAt(right)),left); } bestresult = Math.max(right-left+1,bestresult); character.put(s.charAt(right),right+1); } return bestresult; } }
