法算day8

lief2025-11-242025-11-24

[up主专用，视频内嵌代码贴在这]

无重复字符的最长子串

问题描述

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

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

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

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

算法分析

这个问题使用滑动窗口（双指针）的方法来解决。我们维护一个窗口，窗口内的字符都是不重复的。通过左右两个指针来定义窗口的边界：
右指针不断向右移动，扩展窗口
当遇到重复字符时，左指针向右移动，缩小窗口
在每次扩展窗口后，记录当前窗口的长度，并更新最大长度
这种方法的时间复杂度是O(n)，其中n是字符串的长度，因为每个字符最多被访问两次（一次由右指针，一次由左指针）。空间复杂度是O(min(m, n))，其中m是字符集的大小。

可视化说明(以“abcabcbb”为例)

初始: [a]bcabcbb         窗口: "a"      长度:1
扩展: [ab]cabcbb         窗口: "ab"     长度:2  
扩展: [abc]abcbb         窗口: "abc"    长度:3
遇到重复: a[bca]bcbb     窗口: "bca"    长度:3
遇到重复: ab[cab]cbb     窗口: "cab"    长度:3
遇到重复: abc[abc]bb     窗口: "abc"    长度:3
遇到重复: abca[bc]bb     窗口: "bc"     长度:2
遇到重复: abcab[cb]b     窗口: "cb"     长度:2
遇到重复: abcabc[b]b     窗口: "b"      长度:1
遇到重复: abcabcb[b]     窗口: "b"      长度:1

python版

def lengthOfLongestSubstring(s):
    """
    找出不包含重复字符的最长子串的长度
    使用滑动窗口方法
    """
    # 创建一个集合来存储窗口中的字符，用于快速判断字符是否重复
    char_set = set()
    # 左指针，表示当前窗口的起始位置
    left = 0
    # 记录最长子串的长度
    max_length = 0
    
    # 右指针遍历整个字符串
    for right in range(len(s)):
        # 如果当前字符已经在窗口中存在
        while s[right] in char_set:
            # 从窗口中移除左指针指向的字符
            char_set.remove(s[left])
            # 左指针向右移动，缩小窗口
            left += 1
        
        # 将当前字符添加到窗口中
        char_set.add(s[right])
        # 更新最大长度：当前窗口的长度是 right - left + 1
        max_length = max(max_length, right - left + 1)
    
    return max_length

# 测试代码
if __name__ == "__main__":
    # 示例1
    s1 = "abcabcbb"
    print(lengthOfLongestSubstring(s1))  # 输出: 3
    
    # 示例2
    s2 = "bbbbb"
    print(lengthOfLongestSubstring(s2))  # 输出: 1
    
    # 示例3
    s3 = "pwwkew"
    print(lengthOfLongestSubstring(s3))  # 输出: 3

✅ 说明：

时间复杂度：O(n)，其中n是字符串的长度
空间复杂度：O(min(m, n))，其中m是字符集的大小

java版

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeating {
    public int lengthOfLongestSubstring(String s) {
        // 如果字符串为空或长度为0，直接返回0
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // 使用HashMap来存储字符和它们最近出现的位置
        Map<Character, Integer> charIndexMap = new HashMap<>(); //new HashMap<>(): 创建HashMap类的实例
        //Map<Character, Integer>: 声明一个映射接口，键是Character类型，值是Integer类型;charIndexMap: 变量名
        // 初始化最大长度为0
        int maxLength = 0;
        // 初始化滑动窗口的左边界
        int left = 0;
        
        // 遍历字符串，右指针从0到字符串末尾
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right); //字符串类的方法，用于获取指定位置的字符
            
            // 如果当前字符已经在窗口中出现过
            if (charIndexMap.containsKey(currentChar)) {
                // 更新左边界，确保窗口内没有重复字符
                // 取最大值是为了防止左边界向左移动
                left = Math.max(left, charIndexMap.get(currentChar) + 1);
            }
            
            // 更新当前字符的最新位置
            charIndexMap.put(currentChar, right);
            
            // 计算当前窗口的长度，并更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
    
    // 测试代码
    public static void main(String[] args) {
        LongestSubstringWithoutRepeating solution = new LongestSubstringWithoutRepeating();
        
        // 示例1
        String s1 = "abcabcbb";
        System.out.println("输入: " + s1);
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s1)); // 输出: 3
        
        // 示例2
        String s2 = "bbbbb";
        System.out.println("输入: " + s2);
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s2)); // 输出: 1
        
        // 示例3
        String s3 = "pwwkew";
        System.out.println("输入: " + s3);
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s3)); // 输出: 3
        
        // 额外测试用例
        String s4 = "abcde";
        System.out.println("输入: " + s4);
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s4)); // 输出: 5
        
        String s5 = "aab";
        System.out.println("输入: " + s5);
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s5)); // 输出: 2
    }
}

执行过程

初始状态: left=0, maxLength=0, charIndexMap={}

第1步: right=0, char='a'
  charIndexMap中没有'a'，直接添加
  charIndexMap={'a':0}
  当前窗口长度=1，maxLength=1

第2步: right=1, char='b'
  charIndexMap中没有'b'，直接添加
  charIndexMap={'a':0, 'b':1}
  当前窗口长度=2，maxLength=2

第3步: right=2, char='c'
  charIndexMap中没有'c'，直接添加
  charIndexMap={'a':0, 'b':1, 'c':2}
  当前窗口长度=3，maxLength=3

第4步: right=3, char='a'
  charIndexMap中有'a'，位置是0
  更新left = max(0, 0+1) = 1
  更新charIndexMap中'a'的位置为3
  charIndexMap={'a':3, 'b':1, 'c':2}
  当前窗口长度=3，maxLength=3

第5步: right=4, char='b'
  charIndexMap中有'b'，位置是1
  更新left = max(1, 1+1) = 2
  更新charIndexMap中'b'的位置为4
  charIndexMap={'a':3, 'b':4, 'c':2}
  当前窗口长度=3，maxLength=3

第6步: right=5, char='c'
  charIndexMap中有'c'，位置是2
  更新left = max(2, 2+1) = 3
  更新charIndexMap中'c'的位置为5
  charIndexMap={'a':3, 'b':4, 'c':5}
  当前窗口长度=3，maxLength=3

第7步: right=6, char='b'
  charIndexMap中有'b'，位置是4
  更新left = max(3, 4+1) = 5
  更新charIndexMap中'b'的位置为6
  charIndexMap={'a':3, 'b':6, 'c':5}
  当前窗口长度=2，maxLength=3

第8步: right=7, char='b'
  charIndexMap中有'b'，位置是6
  更新left = max(5, 6+1) = 7
  更新charIndexMap中'b'的位置为7
  charIndexMap={'a':3, 'b':7, 'c':5}
  当前窗口长度=1，maxLength=3

最终结果: 3