Day16-无重复字符的最长子串

🔗 LeetCode 3 - Longest Substring Without Repeating Characters

📌 题目描述

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

示例：

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

---

💡 解题思路

使用 滑动窗口 方法：

1. 使用一个 Set 记录当前窗口内的字符；
2. 定义两个指针 left 和 right，初始都为 0；
3. 如果 s[right] 不在 Set 中，加入 set 并更新最大长度；
4. 如果存在重复字符，移动 left 指针并从 Set 中移除字符，直到不再重复；
5. 重复此过程直到遍历完整个字符串。

时间复杂度：O(n)
空间复杂度：O(n)

---

✅ JavaScript 实现

var lengthOfLongestSubstring = function(s) {
    let set = new Set();
    let left = 0, maxLen = 0;

    for (let right = 0; right < s.length; right++) {
        while (set.has(s[right])) {
            set.delete(s[left]);
            left++;
        }
        set.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
};

---

✅ Swift 实现

func lengthOfLongestSubstring(_ s: String) -> Int {
    var set = Set<Character>()
    var left = s.startIndex
    var maxLength = 0
    var right = left

    while right < s.endIndex {
        if !set.contains(s[right]) {
            set.insert(s[right])
            maxLength = max(maxLength, s.distance(from: left, to: right) + 1)
            right = s.index(after: right)
        } else {
            set.remove(s[left])
            left = s.index(after: left)
        }
    }

    return maxLength
}

---

🧠 思考拓展

• 如何在出现中文字符（Unicode 多字节）时保持算法有效？
• 如果要求输出最长子串本身，而不是长度，应该如何修改代码？
• 如果对性能有极致要求，有哪些方式能减少空间占用？