无重复字符的最长子串

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

思路分析

问题理解

首先要区分两个概念：

子串（Substring）：必须是连续的字符序列，如 "abc" 的子串有 "a", "ab", "abc", "b", "bc", "c"
子序列（Subsequence）：可以不连续，如 "abc" 的子序列包括 "ac"

本题要求的是子串，必须连续。

暴力解法的问题

最直观的想法是：枚举所有子串，检查每个子串是否有重复字符，然后找最长的那个。

时间复杂度：O(n³)
- 枚举起点 i：O(n)
- 枚举终点 j：O(n)  
- 检查 [i,j] 是否有重复：O(n)

这个复杂度太高了，需要优化。

滑动窗口思路

核心观察：如果子串 [i, j] 中出现了重复字符，那么以 i 为起点的更长子串 [i, j+1], [i, j+2]... 必然也有重复。所以我们没必要继续枚举，应该直接移动起点 i。

这就是滑动窗口的思想：

维护一个窗口 [left, right]，保证窗口内没有重复字符
right 不断向右扩展，尝试扩大窗口
当遇到重复字符时，收缩 left，直到窗口内无重复

算法流程

使用 HashMap 记录每个字符最后一次出现的位置
遍历字符串，right 指针不断右移
对于当前字符 c：
- 如果 c 之前出现过，且在当前窗口内（位置 ≥ left），则需要收缩左边界
- 左边界更新为 max(left, 上次出现位置 + 1)，确保窗口内不包含重复的 c
更新 c 的最新位置
更新答案 res = max(res, right - left + 1)

复杂度分析

时间复杂度：O(n)，每个字符最多被访问两次（一次被 right 指向，一次导致 left 跳过）
空间复杂度：O(min(m, n))，其中 m 是字符集大小（如 ASCII 为 128），n 是字符串长度

代码实现

java

/**
 * 题目：3. 无重复字符的最长子串
 * 链接：<a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/">...</a>
 */
public class P3lengthOfLongestSubstring {

    /**
     * 使用滑动窗口算法求解无重复字符的最长子串
     * @param s 输入字符串
     * @return 最长子串的长度
     */
    public int lengthOfLongestSubstring(String s) {
        int left = 0;  // 滑动窗口左边界
        int res = 0;
        // map存储字符及其最新出现的位置索引
        Map<Character, Integer> map = new HashMap<>();

        // right为滑动窗口右边界，不断向右扩展
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            // 如果当前字符已存在于窗口中
            if (map.containsKey(c)) {
                // 将左边界移动到重复字符的下一个位置
                // 使用Math.max确保left只向右移动，不回退
                left = Math.max(left, map.get(c) + 1);
            }

            // 更新当前字符的最新位置
            map.put(c, right);

            // 更新最长子串长度（当前窗口大小 = right - left + 1）
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        P3lengthOfLongestSubstring solution = new P3lengthOfLongestSubstring();

        // 编写简易测试用例
        String testCase = "abcabcbb";
        int result = solution.lengthOfLongestSubstring(testCase);

        System.out.println("Result: " + result);
        assert result == 3 : "Test Case Failed!";
    }
}

无重复字符的最长子串 ​

思路分析 ​

问题理解 ​

暴力解法的问题 ​

滑动窗口思路 ​

算法流程 ​

复杂度分析 ​

代码实现 ​