知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 无重复字符的最长子串 ## 题目(LeetCode 3) 给定一个字符串 s,找出其中不含有重复字符的最长子串的长度。 ``` 输入:s = "abcabcbb" 输出:3("abc") 输入:s = "bbbbb" 输出:1("b") ``` ## 大白话理解 用一个窗口在字符串上滑动,窗口里不能有重复字符。遇到重复的就缩小左边界,一直维护最大窗口长度。 ## 解法:滑动窗口 + 哈希 ```java class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> map = new HashMap<>(); int left = 0, res = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); if (map.containsKey(c)) { // 直接跳到重复字符的下一个位置 left = Math.max(left, map.get(c) + 1); } map.put(c, right); res = Math.max(res, right - left + 1); } return res; } } ``` > 💬 **Q:这里为什么要用 Math.max?** > > 因为 HashMap 没有在字符移出窗口时删除记录,`map.get(c)` 可能返回一个已经在窗口左边的旧索引。不取 max 的话 left 会往回跳,窗口反而变大。 > > 用 `"abba"` 模拟: > ``` > i=0: c='a', map={a:0}, left=0 > i=1: c='b', map={a:0,b:1}, left=0 > i=2: c='b', map里b在1 → left = max(0, 2) = 2 ✓ > i=3: c='a', map里a在0 → map.get('a')+1 = 1 > > 不用 max:left = 1 → 窗口 [1,3]="bba" 包含两个b ✗ > 用了 max:left = max(2, 1) = 2 → 窗口 [2,3]="ba" ✓ > ``` > > `Math.max` 保证 left 只能往右走不能往左退,过滤掉 map 中已经在窗口外的过期记录。 ## 复杂度 - 时间 O(n),空间 O(min(n, 字符集大小)) ## 一句话总结 滑动窗口经典题,右指针扩张,遇到重复字符左指针跳到重复位置的下一个。 --- 下一篇:[02 - LRU缓存](./02-lru-cache.md) ## 解法二:滑动窗口 + 数组(ASCII 优化) 用长度 128 的数组代替 HashMap,适用于 ASCII 字符集,常数更小。 ```java class Solution { public int lengthOfLongestSubstring(String s) { int[] index = new int[128]; // 记录字符上次出现位置+1 int left = 0, res = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); left = Math.max(left, index[c]); res = Math.max(res, right - left + 1); index[c] = right + 1; } return res; } } ``` ## 解法对比 | | 解法一 | 解法二 | |--|--------|--------| | 时间复杂度 | O(n) | O(n) | | 空间复杂度 | O(min(n, 字符集)) | O(1)(固定128) | | 特点 | 通用,支持任意字符 | ASCII 场景常数更小 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入