前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C语言每日一题(38)无重复字符的最长字串

C语言每日一题(38)无重复字符的最长字串

作者头像
对编程一片赤诚的小吴
发布2024-01-23 15:11:43
1300
发布2024-01-23 15:11:43
举报

力扣 3 无重复字符的最长字串

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

代码语言:javascript
复制
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

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

思路分析

关于这道题用滑动窗口的思想来做的话会非常麻烦,既要考虑最长的字串长度,同时还要保证不出现重复字符(考虑窗口里的每一个字符不重复),我们可以用一个非常巧妙的思路

这个思路利用了关于哈希算法以及字符的ascii编码来进行。我们首先定义一个数组名为hash,容量为256的数组,初始化为0。随后开始遍历整个字符串,这里需要两层循环,利用每一个字符的ascii编码当作数组的下标,如果下标对应的值为零,我们设置为1,并进入下面if语句的运行,如果下一个字符和它相等,就不会进入接下来的判断,这是判断不出现重复字符的方法。

关于求最长的字串长度,我们利用两个下标,从第一个字符开始,如果接下来的字符对应的下标的数组为0就进入if语句,此时遍历的两个下标的差值在加上原来的第一个字符(也算不重复的字串)便是不出现重复字符字串的长度,同时定义一个max值保留每一次的最大值即可。

完整代码

代码语言:javascript
复制
int lengthOfLongestSubstring(char* s) {
    int j=0;
    int i=0;
    int max=1;
    int n=strlen(s);
    if(n==0)
    {
        return 0;
    }
    for(i=0;i<n;i++)
    {
        int hash[256]={0};
        for(j=i;j<n;j++)
        {
            if(hash[s[j]]==0)
            {
                hash[s[j]]=1;
                if(j-i+1>max)
                {
                    max=j-i+1;
                }
            }
            else
            {
                break;
            }
        }
    }
    return max;
   
    
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-01-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 思路分析
  • 完整代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档