算法题每日一练---第67天:无重复字符的最长子串

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

3.png

一、问题描述


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


题目链接:无重复字符的最长子串


二、题目要求


样例 1

输入: s="abcabcbb"输出: 3解释: 因为无重复字符的最长子串是"abc",所以其长度为3


样例 2

输入: s="bbbbb"输出: 1解释: 因为无重复字符的最长子串是"b",所以其长度为1


考察

字符串、滑动窗口
建议用时20~35min


三、问题分析


拿到这一题,首先确定属于字符串的应用,以样例 1为例,我一开始的思路是:

从字符串逐个开始遍历,依次向后寻找以当前字符作为首位的最大子串。

abcabcbb第一位aabc第二位bbca第三位ccab第四位aabc......
最后一位bb

我一开始的想法是哈希表(C++的map计数),如果当前这个字符前面的哈希表里面没有出现,那么字符串长度+1,这个字符哈希表+1。按照上面的步骤,逐步遍历。

43.png

但是这种算法效率也太差了,我们优化一下。

41.png

其实可以把原来的二层循环简化到一层,l r作为双指针分别指向第一个字符,依次向后遍历。

如果r指向字符没出现,将它后一位的下标加入哈希表中,l不变,r++。

如果r指向字符出现,l需要变成上一个出现的字符后一位,这样可以保障[l,r]区间内不存在重复的字符。

可以依照力扣上面的几张图示,帮助理解。


四、编码实现


1.优化前

classSolution {
public:
intlengthOfLongestSubstring(strings) {
inti,j,n=s.size(),ans=0,k=0;//初始化代码map<char,int>m;//哈希表存储for(i=0;i<n;i++)//每一个字符作为起点    {
m.clear();//清空ans=0;//for(j=i;j<n;j++)//向后寻找无重复字符        {
if(m[s[j]]==0)//找到了            {
ans++;//计数m[s[j]]++;//标记            }
else//没找到直接退出break;
        }
k=max(k,ans);//寻找最大值    }
returnk;//输出结果    }
};


2.优化后

classSolution {
public:
intlengthOfLongestSubstring(strings) {
intl,r,n=s.size(),ans=0;//初始化变量map<char,int>m;//哈希表for(l=0,r=0;r<n;r++)//区间移动        {
if(m[s[r]]>0)//当前字符与哈希表里面冲突l=max(l,m[s[r]]);//l移位m[s[r]]=r+1;//哈希表存储下标的后一位ans=max(ans,r-l+1);//求出最大值        }
returnans;//输出结果    }
};

五、测试结果42.png

从964ms->12ms,不优化了,满足了。

相关文章
|
2月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
53 0
|
4月前
|
算法
【算法】位运算算法——判断字符是否唯一
【算法】位运算算法——判断字符是否唯一
|
4月前
|
算法
【算法】滑动窗口——无重复字符的最长子串
【算法】滑动窗口——无重复字符的最长子串
|
2月前
|
算法 Java 程序员
【算法每日一练及解题思路】有n级台阶,一次只能上1级或2级,共有多少种走法?
本文深入解析了“爬楼梯问题”,探讨了递归与迭代两种解法,并提供了Java代码实现。通过分析问题本质,帮助读者理解动态规划技巧,提高解决实际编程问题的能力。关键词:Java, 算法, 动态规划, 爬楼梯问题, 递归, 迭代。
117 0
|
7月前
|
算法 C++
【优选算法】——滑动窗口——3. 无重复字符的最长子串
【优选算法】——滑动窗口——3. 无重复字符的最长子串
|
6月前
|
算法
数据结构和算法——散列函数的构造方法(直接定址法、除留余数法、数字分析法、折叠法、平方取中法、ASCII码加和法、前三字符移位法)
数据结构和算法——散列函数的构造方法(直接定址法、除留余数法、数字分析法、折叠法、平方取中法、ASCII码加和法、前三字符移位法)
74 0
|
7月前
|
人工智能 算法 测试技术
【字符串】【C++算法】828.统计子串中的唯一字符
【字符串】【C++算法】828.统计子串中的唯一字符
|
17天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
23天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
3天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。