不含重复字符的最长子串：暴力解法 vs 滑动窗口
🧩 题目描述
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
示例
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: s = "bbbbb"
输出: 1
解释: 最长子串是 "b"。
输入: s = "pwwkew"
输出: 3
解释: 最长子串是 "wke"，注意 "pwke" 是子序列不是子串。
🚫 暴力解法
思路
枚举所有可能的子串，逐个判断是否包含重复字符。
Swift 实现
func lengthOfLongestSubstringBruteForce(_ s: String) -> Int {
let chars = Array(s)
var maxLength = 0
for i in 0..<chars.count {
var seen = Set<Character>()
var j = i
while j < chars.count, !seen.contains(chars[j]) {
seen.insert(chars[j])
j += 1
}
maxLength = max(maxLength, j - i)
}
return maxLength
}
时间复杂度
- 时间：
O(n^2)，其中n是字符串长度。 - 空间：
O(min(n, m))，m是字符集大小（如 ASCII 为 128）。
✅ 滑动窗口解法
思路
使用一个窗口 [left, right] 表示当前无重复字符的子串：
right不断右移扩展窗口- 遇到重复字符时，移动
left缩小窗口
Swift 实现
func lengthOfLongestSubstring(_ s: String) -> Int {
var charIndexMap = [Character: Int]()
var maxLength = 0
var left = 0
for (right, char) in s.enumerated() {
if let prevIndex = charIndexMap[char], prevIndex >= left {
left = prevIndex + 1
}
charIndexMap[char] = right
maxLength = max(maxLength, right - left + 1)
}
return maxLength
}
时间复杂度
- 时间：
O(n)，每个字符最多访问两次。 - 空间：
O(min(n, m))
📊 性能对比
| 解法 | 时间复杂度 | 空间复杂度 | 是否适合大数据量 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(min(n, m)) | ❌ 性能低 |
| 滑动窗口优化 | O(n) | O(min(n, m)) | ✅ 高效 |
📌 总结
- 暴力解法易于理解但性能差，仅适用于小规模数据。
- 滑动窗口算法利用哈希表快速判断重复字符，大幅提升效率。
- 本题是滑动窗口技巧的典型应用，适合入门字符串处理优化技巧。
👨💻 喜欢这类解题解析？关注我带你继续刷题与优化思路！