Day 8 - 字符串进阶

📅 日期：2026年1月15日
🎯 主题：字符串进阶 + 滑动窗口与字符统计

今日题目

题目1：无重复字符的最长子串 (Longest Substring Without Repeating Characters)

难度：⭐⭐ 中等

链接：LeetCode 3. 无重复字符的最长子串

题目描述

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

示例：

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

输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

解题思路

方法一：滑动窗口 + 哈希表 ✅ 推荐

核心思想：

1. 使用滑动窗口维护一个不含重复字符的子串
2. 用哈希表（或数组）记录当前窗口中每个字符最后一次出现的位置
3. 右指针 right 不断向右扩展，将新字符加入窗口
4. 若新字符已存在于窗口中（且其上次出现位置在窗口内），则移动左指针 left 到「该字符上次出现位置的下一个位置」，保证窗口内无重复
5. 每次扩展后更新最长长度

关键点：

• 窗口为 [left, right]，左闭右闭
• 重复时：left = Math.max(left, lastIndex.get(c) + 1)
• 时间复杂度：O(n)；空间复杂度：O(min(m, n))，m 为字符集大小

方法二：滑动窗口 + 集合

核心思想：

1. 用 Set 维护当前窗口内的字符
2. 右指针扩展时若字符已在 Set 中，则左指针右移并从 Set 中移除对应字符，直到无重复
3. 再将该字符加入 Set，更新长度

代码实现

方法一：滑动窗口 + 哈希表

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // 记录每个字符最后一次出现的位置
        Map<Character, Integer> lastIndex = new HashMap<>();
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // 若该字符在窗口内已出现，则收缩左边界
            if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
                left = lastIndex.get(c) + 1;
            }

            lastIndex.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

方法二：滑动窗口 + 集合

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        Set<Character> window = new HashSet<>();
        int maxLen = 0;
        int left = 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;
    }
}

复杂度分析

• 时间复杂度：O(n)，每个字符最多被访问两次（左、右指针各一次）
• 空间复杂度：O(min(m, n))，m 为字符集大小，n 为字符串长度

---

题目2：字符串中的第一个唯一字符 (First Unique Character in a String)

难度：⭐ 简单

链接：LeetCode 387. 字符串中的第一个唯一字符

题目描述

给定一个字符串 s，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

输入：s = "leetcode"
输出：0
解释：'l' 是第一个不重复的字符。

输入：s = "loveleetcode"
输出：2
解释：'v' 是第一个不重复的字符。

输入：s = "aabb"
输出：-1
解释：不存在不重复的字符。

提示：

• 1 <= s.length <= 10^5
• s 只包含小写字母

解题思路

方法一：两次遍历 + 频率数组 ✅ 推荐

核心思想：

1. 第一次遍历：用数组（或哈希表）统计每个字符出现的次数
2. 第二次遍历：按顺序找第一个出现次数为 1 的字符，返回其下标
3. 若没有则返回 -1

关键点：

• 字符均为小写字母时，可用长度为 26 的数组，下标为 c - 'a'
• 时间复杂度：O(n)；空间复杂度：O(1)（字符集固定）

方法二：哈希表记录索引

核心思想：

1. 用哈希表记录每个字符第一次出现的索引；若再次出现可设为 -1 或特殊值
2. 遍历哈希表，找索引有效且最小的那个
3. 也可先统计频率，再遍历找第一个频率为 1 的字符

代码实现

方法一：两次遍历 + 频率数组

class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }

        // 统计每个字符出现的次数（仅小写字母）
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
        }

        // 按顺序找第一个出现次数为 1 的字符
        for (int i = 0; i < s.length(); i++) {
            if (freq[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }

        return -1;
    }
}

方法二：哈希表记录索引

import java.util.*;

class Solution {
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }

        Map<Character, Integer> indexMap = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 若已出现则标记为 -1，否则记录首次出现位置
            indexMap.put(c, indexMap.containsKey(c) ? -1 : i);
        }

        int first = s.length();
        for (int idx : indexMap.values()) {
            if (idx != -1 && idx < first) {
                first = idx;
            }
        }

        return first == s.length() ? -1 : first;
    }
}

复杂度分析

• 时间复杂度：O(n)，两次遍历字符串
• 空间复杂度：
  • 频率数组：O(1)，固定 26 个字母
  • 哈希表：O(1)，字符集大小有限

---

今日总结

学到了什么？

1. 滑动窗口：用左右指针维护一段连续区间，处理「无重复子串」类问题
2. 哈希表记录位置：用 Map 存字符最后一次出现下标，实现 O(1) 收缩左边界
3. 字符统计：用固定长度数组统计小写字母频率，空间 O(1)
4. 两次遍历：先统计再按顺序找第一个满足条件的下标

关键技巧

技巧	适用场景	时间复杂度	空间复杂度
滑动窗口+哈希表	无重复/最多 K 个等子串	O(n)	O(min(m,n))
频率数组	小写字母/数字统计	O(n)	O(1)
两次遍历	第一个满足条件的元素	O(n)	O(1)

字符串进阶要点

1. 滑动窗口：

   • 右指针扩展、左指针在满足条件时收缩
   • 用 Map/Set 维护窗口内字符，避免重复

2. 字符统计：

   • 仅小写字母：int[] freq = new int[26]，下标 c - 'a'
   • 含大小写/数字：可扩大数组或用 HashMap

3. 常见错误：

   • 收缩左边界时写成 left = lastIndex.get(c) + 1 而未与当前 left 取 max，导致左指针回退
   • 忘记空串或单字符等边界
   • 第一个唯一字符要在原串顺序下找，不能只看哈希表中最小的索引（若用索引法需保证顺序）

相似题目推荐

• 至多包含 K 个不同字符的最长子串 - 滑动窗口
• 最小覆盖子串 - 滑动窗口进阶
• 重复的 DNA 序列 - 哈希表 + 子串
• 有效的字母异位词 - 字符统计

明日计划

• Day 9 双指针
• 练习：两数之和 II、三数之和等双指针经典题