LeetCode-Go 题解0003. Longest Substring Without Repeating Characters无重复字符的最长子串与滑动窗口三解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode-Go 仓库中 0003. Longest-Substring-Without-Repeating-Characters 一题展开系统讲解无重复字符的最长子串的滑动窗口核心思想并结合仓库源码逐行剖析位图、频率数组、哈希桶三种 Go 实现及其复杂度差异。读完本文你将掌握滑动窗口这一高频字符串/数组技巧能独立写出可运行、可通过测试的 Go 解法并理解它与第 76、438、567 题的家族关联。题目在一个字符串中寻找没有重复字母的最长子串给定一个字符串找出其中不含重复字符的最长子串的长度。注意题目要求的是子串substring必须是原字符串中连续的一段而不是子序列subsequence。例如pwke是pwwkew的子序列但因为它跳过了重复的w并不是连续的子串因此不满足题意。三个官方示例Input: abcabcbb Output: 3 Explanation: The answer is abc, with the length of 3. Input: bbbbb Output: 1 Explanation: The answer is b, with the length of 1. Input: pwwkew Output: 3 Explanation: The answer is wke, with the length of 3. Note that the answer must be a substring, pwke is a subsequence and not a substring.边界情况空字符串的最长子串长度为 0仓库测试用例中已显式覆盖此场景见下文测试小节。核心思路滑动窗口Sliding Window该题的标准解法是滑动窗口。原文档给出的思路可以概括为右边界持续右移扩张只要窗口内没有重复字符就不断向右扩大窗口出现重复则收缩左边界一旦检测到重复字符就缩小左边界直到重复字符被移出窗口每次移动后更新答案计算当前窗口长度right - left并判断是否需要更新全局最大值。整个过程右指针每个字符至多被访问一次左指针同理因此整体时间复杂度为 O(n)。源码级拆解仓库中的三种 Go 实现LeetCode-Go 仓库在 3. Longest Substring Without Repeating Characters.go 中给出了三种解法分别是位图、频率数组滑动窗口、哈希桶。解法一位图bitSet双指针// 解法一 位图 func lengthOfLongestSubstring(s string) int { if len(s) 0 { return 0 } var bitSet [256]bool result, left, right : 0, 0, 0 for left len(s) { // 右侧字符对应的 bitSet 被标记 true说明此字符在 X 位置重复需要左侧向前移动直到将 X 标记为 false if bitSet[s[right]] { bitSet[s[left]] false left } else { bitSet[s[right]] true right } if result right-left { result right - left } if leftresult len(s) || right len(s) { break } } return result }实现要点用[256]bool位图记录当前窗口内出现过的字符覆盖 ASCII 全部取值s[i]作为 byte 直接索引当bitSet[s[right]]为true说明right处字符已在窗口内出现过此时只动左指针清除s[left]的标记并left直到重复字符被移出否则标记s[right]并右移右指针扩张窗口每次循环都尝试用right - left更新result并带有提前终止剪枝leftresult len(s)剩余可探索长度已不可能超过当前答案或right len(s)右边界越界时直接跳出。位图只记录有没有不记录在哪个位置因此收缩时需要逐个字符地清除标记这也是它比哈希桶版多付出一些左移开销的原因。解法二频率数组 经典滑动窗口模板// 解法二 滑动窗口 func lengthOfLongestSubstring1(s string) int { if len(s) 0 { return 0 } var freq [127]int result, left, right : 0, 0, -1 for left len(s) { if right1 len(s) freq[s[right1]] 0 { freq[s[right1]] right } else { freq[s[left]]-- left } result max(result, right-left1) } return result }实现要点right初始化为-1表示空窗口当right1 len(s)且下一个字符s[right1]的频率为 0 时说明窗口可以无重复地向右扩展频率加一、right否则说明窗口已无法扩张要么右边界到顶要么下一个字符会引入重复于是收缩左边界s[left]频率减一、left每次迭代用max(result, right-left1)更新答案。这一版的写法与仓库中第 76 题 Minimum Window Substring 的骨架高度一致同样是能扩则扩、不能扩则缩左边界、每轮更新候选答案只是第 76 题多维护了一个命中计数count。对比阅读这两份源码可以快速掌握滑动窗口类题目的通用模板。解法三哈希桶记录最近出现位置// 解法三 滑动窗口-哈希桶 func lengthOfLongestSubstring2(s string) int { right, left, res : 0, 0, 0 indexes : make(map[byte]int, len(s)) for left len(s) { if idx, ok : indexes[s[left]]; ok idx right { right idx 1 } indexes[s[left]] left left res max(res, left-right) } return res }实现要点用map[byte]int记录每个字符最近一次出现的位置遍历时若s[left]之前出现过且其位置idx不小于当前左窗口right说明idx处的字符在窗口内重复了直接将right跳到idx 1一次性跳过重复段无需逐字符收缩每轮更新该字符的最新位置并用left - right当前窗口长度刷新res。与解法一/二相比哈希桶通过位置索引实现了左指针的跳跃式移动是三种写法中单次收缩成本最低的版本平均常数也更小代价是引入了 map 的额外内存与哈希计算开销。复杂度对比解法时间空间特点位图双指针O(n)O(1)[256]bool固定 256 字节逐字符收缩适合 ASCII 输入频率数组滑动窗口O(n)O(1)[127]int固定数组模板化最强易推广到 76/438/567哈希桶O(n)O(k)k 为字符集大小左指针跳跃式收缩常数最优注位图与频率数组均为固定大小数组不随输入规模增长故空间视为 O(1)哈希桶的空间随去重后字符数量线性增长。测试用例与运行验证仓库为本题提供了单元测试 3. Longest Substring Without Repeating Characters_test.go覆盖四个用例输入期望输出说明abcabcbb3最长子串abcbbbbb1全部字符重复pwwkew3最长子串wke非pwke0空串边界测试代码同时调用lengthOfLongestSubstring、lengthOfLongestSubstring1、lengthOfLongestSubstring2三个版本确保三种实现行为一致测试驱动采用结构体question3{para3, ans3}组织输入与期望输出这也是仓库中所有题解统一使用的表格驱动风格。本地运行该测试的方式项目基于 Go 1.19见 go.mod# 在仓库根目录运行全部题解测试 go test ./leetcode/0003.Longest-Substring-Without-Repeating-Characters/... # 或单独执行本题测试函数输出 input/output 对 go test -v -run Test_Problem3 ./leetcode/0003.Longest-Substring-Without-Repeating-Characters/...仓库根目录的 gotest.sh 提供了全量覆盖率测试脚本go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...生成的 coverage.txt 可用于验证包括本题在内所有题解的覆盖情况。一题带一系滑动窗口题型家族原文档明确指出本题与第 438、76、567 题思路同源均基于滑动窗口。在仓库中可以对照以下源码加深理解第 76 题 Minimum-Window-Substring在s中找到覆盖t全部字符的最短子串通过tFreq/sFreq双频率数组与命中计数count完成窗口收缩判定是求最短合法窗口的代表第 438 题 Find-All-Anagrams-in-a-String在s中找出p的所有字母异位词起始下标固定窗口长度len(p)属于固定长度窗口变体第 567 题 Permutation-in-String判断s2是否包含s1的任一排列与 438 题思路几乎一致。它们的共性是用频率数组/哈希表维护窗口内字符状态双指针移动窗口每轮更新答案。掌握本题的三种实现后再读 76/438/567 的源码会非常顺畅——这也是 LeetCode-Go 仓库按题型家族组织题解、便于横向对照的设计初衷。小结本题核心是滑动窗口右指针扩张、遇重收缩左指针、逐轮更新最长长度仓库给出了位图、频率数组、哈希桶三种 Go 实现分别体现了逐字符收缩与跳跃式收缩两种收缩策略复杂度均为 O(n)空串返回 0 的边界处理、ASCII 字符用定长数组索引、map 记录最近位置等细节都是面试与工程中高频复用的写法本题与 76、438、567 构成滑动窗口题型家族可在 leetcode 目录下对照阅读形成体系化记忆。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
