当前位置: 首页 > article >正文

LeetCode热题100(七)—— 3.无重复字符的最长子串

LeetCode热题100(七)—— 3.无重复字符的最长子串

  • 题目描述
  • 代码实现
  • 思路解析

  • 你好,我是杨十一,一名热爱健身的程序员
  • 在Coding的征程中,不断探索与成长
  • LeetCode热题100——刷题记录(不定期更新)
    此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
    愿与诸君共同探讨,在代码世界里携手共进,攻克难题,提升自我

题目描述

给定一个字符串 s ,请你找出其中不含有重复字符的最长子串的长度。
示例 1:
        输入: s = "abcabcbb"
        输出: 3 
        解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
        输入: s = "bbbbb"
        输出: 1
        解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
        输入: s = "pwwkew"
        输出: 3
        解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
        请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
        0 <= s.length <= 5 * 104
        s 由英文字母、数字、符号和空格组成

代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) return s.length();

        int L = 0;
        int R = 1;
        int maxLen = 1;

        Set<Character> set = new HashSet<>();
        set.add(s.charAt(0));

        while (R < s.length()) {
            char ch = s.charAt(R);
            if (set.contains(ch)) {
                maxLen = Math.max(maxLen, R - L);
                set.remove(ch);
                while (s.charAt(L) != ch) {
                    set.remove(s.charAt(L++));
                };
                set.remove(s.charAt(L++));
            }
            set.add(s.charAt(R));
            R++;
        }
        return Math.max(maxLen, R - L);
    }
}

思路解析

  1. 输入:字符串
  2. 输出:最长不重复子串的长度
  3. 思路:双指针 + 哈希集合
    • 子串长度:双指针固定左指针,右指针右移直到出现重复字符串
    • 重复判断:哈希集合存储子串字符,判断右指针移动下一个位置的字符是否重复
    • 如果重复:
      • 记录当前 [L,R) 之间的子串长度,并判断是否是最大子串长度
      • 左指针 L 右移直至子串中重复字符的下一个位置,作为新的子串起点
        在这里插入图片描述
    • 时间复杂度: O ( n ) O(n) O(n)
      • 左指针和右指针各遍历字符串一次 O ( 2 n ) = O ( n ) O(2n) =O(n) O(2n)=O(n)
      • 虽然是双层循环,但不是 n 2 n^2 n2
      • LR指针移动时,另外一个指针固定不移动,并非R或L每移动1次,另一个指针就遍历一遍
    • 空间复杂度: O ( n ) O(n) O(n),也有解释是 O ( ∣ Σ ∣ ) O(|\Sigma|) O(∣Σ∣)
      • 区别在于重复字符是否算作同一个空间。如上,字符c出现2次,哈希集合删除后再添加算作使用了2个空间,两个指针遍历字符串,所有字符都会添加进哈希集合中(部分会在过程中删除)
      • 官方解释:其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在 [0,128) 内的字符,即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符,而字符最多有 ∣Σ∣ 个,因此空间复杂度为 O(∣Σ∣)

  • 你好,我是杨十一,一名热爱健身的程序员
  • 在Coding的征程中,不断探索与成长
  • LeetCode热题100——刷题记录(不定期更新)
    此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
    愿与诸君共同探讨,在代码世界里携手共进,攻克难题,提升自我
原文地址:https://blog.csdn.net/Young_4/article/details/145380852
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/522375.html

相关文章:

  • HttpClient学习
  • 【C语言】内存函数
  • 本地部署deepseek模型步骤
  • Oracle迁移DM数据库
  • PostgreSQL 约束
  • Excel - Binary和Text两种Compare方法
  • OpenAI的真正对手?DeepSeek-R1如何用强化学习重构LLM能力边界——DeepSeek-R1论文精读
  • Ubuntu Server连接wifi
  • CSS-in-JS详解
  • 【C++数论】880. 索引处的解码字符串|2010
  • 一个小小的个人博客系统
  • GraphQL 教程
  • c语言网 1130数字母
  • DDD 分层架构实战指南:从项目结构到落地挑战
  • DeepSeek R1:推理模型新纪元与价格战
  • 【2025最新计算机毕业设计】基于SSM房屋租赁平台【提供源码+答辩PPT+文档+项目部署】(高质量源码,可定制,提供文档,免费部署到本地)
  • 解除阿里云盘压缩包分享限制的最新工具(2025年更新)
  • Node相关配置迁移
  • Node.js下载安装及环境配置
  • 使用脚本执行地理处理工具
  • SCI绘图技巧(2):MATLAB中自定义Colormap及其调用方法
  • 【go语言】数组和切片
  • C语言导航 8.*自定义类型
  • Linux:文件与fd(未被打开的文件)
  • 论文阅读笔记:VMamba: Visual State Space Model
  • 滤波电路汇总