栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode刷题笔记(Java实现)-- 3. 无重复字符的最长子串

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode刷题笔记(Java实现)-- 3. 无重复字符的最长子串

题目难度:Medium

题目要求:
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

##哈希集合
两个指针,分别表示子串的左右边界,
左指针不动,右指针不断右移,每次将一个字符加入哈希集合,并且判断,是否和原集合中的字符重复;
如果重复,就输出当前的非重复的字符长度,然后左指针右移一位,再寻找新的不重复的子串,
最后从所有不重复子串的长度中选出最长的长度返回。


// @lc code=start
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //哈希集合,记录每个字符是否出现过
        Setocc=new HashSet();
        int n = s.length();
        //右指针,初始值为-1,相当于在字符串的左边界的左侧,还没有开始移动
        int rk=-1,ans=0;
        for(int i=0;i 

**复杂度分析:

时间复杂度:O(N),其中 N是字符串的长度。左指针和右指针分别会遍历整个字符串一次。空间复杂度:O(∣Σ∣),其中 Σ 表示字符集(即字符串中可以出现的字符),∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 ASCII 码在[0,128) 内的字符,即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符,而字符最多有∣Σ∣ 个,因此空间复杂度为 O(∣Σ∣)。

**

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/716533.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号