知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 无重复字符的最长子串 ## 题目(LeetCode 3) 给定字符串 s,找出不含重复字符的最长子串的长度。 ``` 输入:"abcabcbb" → 输出:3("abc") 输入:"bbbbb" → 输出:1("b") 输入:"pwwkew" → 输出:3("wke") ``` ## 大白话理解 维护一个窗口,窗口内不能有重复字符。右指针往右扩,遇到重复的就把左指针往右缩,直到窗口内没有重复。 ## 代码 ```java public int lengthOfLongestSubstring(String s) { Set<Character> window = new HashSet<>(); int left = 0, maxLen = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 窗口内有重复,收缩左边 while (window.contains(c)) { window.remove(s.charAt(left)); left++; } window.add(c); maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } ``` ### 优化:用数组记录字符最后出现的位置 ```java public int lengthOfLongestSubstring(String s) { int[] lastIndex = new int[128]; // ASCII Arrays.fill(lastIndex, -1); int left = 0, maxLen = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 如果字符上次出现在窗口内,直接跳过去 if (lastIndex[c] >= left) { left = lastIndex[c] + 1; } lastIndex[c] = right; maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } ``` ## 模拟 ``` s = "abcabcbb" right=0 'a': window={a}, maxLen=1 right=1 'b': window={a,b}, maxLen=2 right=2 'c': window={a,b,c}, maxLen=3 right=3 'a': 重复!left 移到 1, window={b,c,a}, maxLen=3 right=4 'b': 重复!left 移到 2, window={c,a,b}, maxLen=3 right=5 'c': 重复!left 移到 3, window={a,b,c}, maxLen=3 right=6 'b': 重复!left 移到 5, window={c,b}, maxLen=3 right=7 'b': 重复!left 移到 7, window={b}, maxLen=3 答案:3 ``` ## 复杂度 - 时间:O(n) - 空间:O(min(n, 字符集大小)) ## 一句话总结 HashSet 记录窗口内字符,遇到重复就收缩左边界。 --- 上一篇:[01 - 模板](./01-template.md) | 下一篇:[03 - 最小覆盖子串](./03-min-window.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入