JAVA练习276-无重复字符的最长子串

题目概览给定一个字符串s请你找出其中不含有重复字符的最长 子串的长度。示例 1:输入:s abcabcbb输出:3解释:因为无重复字符的最长子串是abc所以其长度为 3。注意 bca 和 cab 也是正确答案。示例 2:输入:s bbbbb输出:1解释:因为无重复字符的最长子串是b所以其长度为 1。示例 3:输入:s pwwkew输出:3解释:因为无重复字符的最长子串是wke所以其长度为 3。 请注意你的答案必须是子串的长度pwke是一个子序列不是子串。提示0 s.length 5 * 104s由英文字母、数字、符号和空格组成来源3. 无重复字符的最长子串 - 力扣LeetCode解题分析方法滑动窗口定义双指针 i 和 j 指向开始的字母用一个集合 set 存储 i 和 j 范围内的所有字母如果 j 指向的字母在 set 里面没有j 就往右边移动如果 set 里有该字母则 i 移动到前一个该字母右边一个字母的位置然后移除 set 中 i 移动过程中指向的字母每次移动记录 i 和 j 最大的差值即可。时间复杂度O(n)空间复杂度O(m) m 为不同字母的个数 class Solution { public int lengthOfLongestSubstring(String s) { char[] cs s.toCharArray(); int i 0, j 0, res 0; HashSetCharacter set new HashSet(); while(i cs.length j cs.length) { if (set.contains(cs[j])) { while (cs[i] ! cs[j]) { set.remove(cs[i]); i; } set.remove(cs[i]); i; } else { set.add(cs[j]); j; } res Math.max(res, j - i); } return res; } }