滑动窗口

无重复字符的最长子串

中等#3Java时间 O(n)空间 O(字符集大小)

题目要做什么

返回字符串中不包含重复字符的最长连续子串长度。子串必须连续,空字符串的答案为 0。

题目示例输入s = "abcabcbb"
题目示例输出3

01 为什么这样做

右指针加入字符,last 保存每个字符上次出现的位置。如果它落在当前窗口内,直接把左边界移到上次位置之后。

始终成立的条件

窗口 [left, right] 中的字符始终互不重复,left 只向右移动。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int lengthOfLongestSubstring(String s) {3        Map<Character, Integer> last = new HashMap<>();4        int left = 0, best = 0;5        for (int right = 0; right < s.length(); right++) {6            char c = s.charAt(right);7            left = Math.max(left, last.getOrDefault(c, -1) + 1);8            last.put(c, right);9            best = Math.max(best, right - left + 1);10        }11        return best;12    }13}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索