首页 > 其他分享 >【LeetCode Hot 100】3. 无重复字符的最长子串

【LeetCode Hot 100】3. 无重复字符的最长子串

时间:2024-09-14 13:13:47浏览次数:10  
标签:子串 int res len st Hot 100 LeetCode 指针

题目描述

本题我最开始的想法就是使用双指针与滑动窗口,滑动过程中维护一个集合,集合内保存滑动窗口内部的所有字符,右边的指针每指向一个新的元素,就判断该元素(字符)是否在集合内,如果已经存在,就说明此时将要出现重复字符,以及无重复字符的子串已经达到了最长的长度,之后我们需要移动左边的指针,直到集合内不存在重复字符,进入下一个循环。

为什么这种方法是正确的?这个题目最直接的想法应该是:从左往右遍历每个元素,尝试以该元素起始的无重复字符的子串的长度。假设以下标l的元素开始的最长子串的右边元素下标为r,说明下一个下标为r + 1的元素在[l, r]的子串中已经存在了,此时我们如果再向右移动左侧指针一个位置,将右侧指针重置为左侧指针旁边一个位置,然后重新开始尝试,已经没有意义了,因为新子串的中间一部分我们之前已经尝试过了。我们可以直接固定右侧指针,移动左侧指针直到没有重复元素,以此时的位置作为起点开始尝试,这样减少了一部分尝试次数。

// C++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        if (len == 0 || len == 1) {
            return len;
        }

        int l = 0, r = 0;
        unordered_set<char> st;
        int res = 0;
        while (r < len) {
            while (r < len && st.find(s[r]) == st.end()) {
                st.insert(s[r]);
                r++;
            }
            int cnt = r - l;
            res = res > cnt ? res : cnt;
            if (r >= len) {
                break;
            }
            while (l < r && st.find(s[r]) != st.end()) {
                st.erase(s[l]);
                l++;
            }
        }
        return res;
    }
};

// Java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len == 0 || len == 1) {
            return len;
        }

        int l = 0, r = 0;
        Set<Character> set = new HashSet<>();
        int res = 0;
        while (r < len) {
            while (r < len && set.contains(s.charAt(r)) == false) {
                set.add(s.charAt(r));
                r++;
            }
            int cnt = r - l;
            res = res > cnt ? res : cnt;
            if (r >= len) {
                break;
            }
            while (l < r && set.contains(s.charAt(r)) == true) {
                set.remove(s.charAt(l));
                l++;
            }
        }
        return res;
    }
}

当然,我们永远需要注意,字符串(数组)的下标不要越界。

标签:子串,int,res,len,st,Hot,100,LeetCode,指针
From: https://www.cnblogs.com/louistang0524/p/18413778

相关文章

  • LeetCode 2390. 从字符串中移除星号(字符串、栈)
    题目:2390.从字符串中移除星号思路:使用栈就可以,这里string也可以实现栈的效果classSolution{public:stringremoveStars(strings){stringe="";for(autox:s){if(x=='*')e.pop_back();elsee.push_back(x);......
  • ChatGPT实战100例 - (21) 搞定汉字新解,o1-mini 在李继刚老师这扳回一局
    文章目录搞定汉字新解,o1-mini在李继刚老师这扳回一局翻车开车飙车出图福利在这福利+1搞定汉字新解,o1-mini在李继刚老师这扳回一局昨天朋友圈刷爆了李继刚老师的汉字新解,废话不说,上prompt;;作者:李继刚;;版本:0.1;;模型:ClaudeSonnet;;......
  • 开源模型应用落地-qwen2-7b-instruct-LoRA微调-unsloth(让微调起飞)-单机单卡-V100(十七)
    一、前言  本篇文章将在v100单卡服务器上,使用unsloth去高效微调QWen2系列模型,通过阅读本文,您将能够更好地掌握这些关键技术,理解其中的关键技术要点,并应用于自己的项目中。  使用unsloth能够使模型的微调速度提高2-5倍。在处理大规模数据或对时间要求较高的场景下......
  • 【LeetCode 算法笔记】49. 字母异位词分组
    目录问题描述计数法:计数法(用哈希表):排序法:问题描述给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=[“eat”,“tea”,“tan”,“ate”,“nat”......
  • 【随想录day2】LeetCode209长度最小的子数组 | LeetCode59螺旋矩阵
    LeetCode209长度最小的子数组1、题目:给定一个含有n个正整数的数组和一个正整数s,找出该数组中满足其和≥s的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回0示例:输入:s=7,nums=[2,3,1,2,4,3]输出:2解释:子数组[4,3]是该条件下的长度最小......
  • 【安全运营】揭秘100个网络风险解决秘籍,让你安全畅游网络世界,不再怕风险!
    01账号密码安全(14条)如果有初始密码,应尽快修改;密码长度不少于8个字符;不要使用单一的字符类型,例如只用小写字母或只用数字;用户名与密码不要使用相同字符;常见的弱口令尽量避免设置为密码;自己、家人、朋友、亲戚、宠物的名字避免设置为密码;生日、结婚纪念日、电话号码等个人信......
  • (nice!!!)LeetCode 2398. 预算内的最多机器人数目(队列、滑动窗口)
    题目:2398.预算内的最多机器人数目思路:双端队列+滑动窗口。因为需要找连续的机器人,这里就需要用到滑动窗口。细节看注释,时间复杂度0(n)。classSolution{public:intmaximumRobots(vector<int>&chargeTimes,vector<int>&runningCosts,longlongbudget){......
  • 【LeetCode Hot 100】2. 两数相加
    题目描述题目手下留情给出的链表使用逆序表示加数,因此我们可以从链表头开始逐位相加。我总结了一下有几点需要注意:显然加法需要注意进位,此外需要格外注意的是最后一位没有加数时,还需要考虑进位是否被置位,如果最后的进位为1,我们还需要创建一个新的节点。当其中一个链表走完,需要......
  • 【每日一题】LeetCode 2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和
    【每日一题】LeetCode2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和、堆(优先队列))题目描述给定两个整数数组chargeTimes和runningCosts,分别代表n个机器人的充电时间和运行成本。再给定一个整数budget,表示预算。我们需要计算在不超过预算的情况下,最......
  • msvcr100.dll丢失导致快吧迷你页异常?深度解析快吧迷你页msvcr100.dll文件丢失原因与修
    在使用快吧迷你页等软件时,有时会遇到“msvcr100.dll丢失”的错误提示,导致软件无法正常运行。这一问题主要由msvcr100.dll文件丢失或损坏引起,该文件是MicrosoftVisualC++2010RedistributablePackage中的一个重要组件,负责提供程序运行所需的运行时库支持。以下是对该问题的......