无重复字符的最长子串

题目

添加链接描述

给定一个字符串 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 由英文字母、数字、符号和空格组成

滑动窗口+Set

/*** 滑动窗口+Set*/
private static int lengthOfLongestSubstring(String s) {if (s == null) {return 0;}int length = s.length();// 将当前窗口 [left, right) 中字符存储在 HashSet 中Set<Character> characterSet = new HashSet<>(length);int left = 0, right = 0, ans = 0;while(left < length && right < length) {char c = s.charAt(right);if (!characterSet.contains(c)) {// 滑动窗口[left, right)字符没有重复，字符c添加进setcharacterSet.add(c);// 滑动窗口left不动，right右移一位right++;// 更新无重复子串长度ans：滑动窗口[left, right)的长度=right-leftans = Math.max(ans, right-left);} else {// 存在字符重复，说明滑动窗口 [left, right) 中存在与 c 相等的字符// set集合中删除字符串left处的元素，这里无法直接定位到重复字符的下标，需要从left开始删除到重复位置characterSet.remove(s.charAt(left));// 滑动窗口right不动，left右移一位，循环执行到重复元素被删除left++;}}return ans;
}

优化的滑动窗口+HashMap

如果 s[right] 在 [left，right) 范围内有与​ s[k] 重复的字符，不需要逐渐增加 left 。 可以直接跳过 [left，k] 范围内的所有元素，并将 left 变为 k+1

/**
* 滑动窗口+HashMap
*/
private static int lengthOfLongestSubstring2(String s) {if (s == null) {return 0;}int length = s.length();// 将当前窗口 [left, right) 中字符存储在 HashMap 中// key：字符，value：字符下标HashMap<Character, Integer> map = new HashMap<>(length);int ans = 0;for (int left = 0, right = 0; right < length; right++) {// 滑动窗口右指针位置char c = s.charAt(right);// 判断字符c是否出现过Integer index = map.get(c);// 字符c重复，索引index，当前左指针left// 左指针直接跳转到index+1位置，s[index] == s[right]// 但是不能超过当前left，取max(index+1, left)// 0 1 2 3 4 5 6 7 8// a b c d c e b g h//         l   r// 此时 left 索引为 4，right 遍历到 b，b重复，对应索引 1, 此时不能回溯，left不变if (Objects.nonNull(index)) {left = Math.max(index + 1, left);}// 计算当前子串长度ans = Math.max(ans, right-left+1);// 当前字符加入map集合，如果存在就用当前下标right覆盖map.put(c, right);}return ans;
}