前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode-3.无重复字符的最长子串 利用一个整形数组+ASCII码实现滑动窗口

LeetCode-3.无重复字符的最长子串 利用一个整形数组+ASCII码实现滑动窗口

原创
作者头像
扎克蕉
修改2020-07-20 10:01:41
2890
修改2020-07-20 10:01:41
举报

先看题目

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

示例 :

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

分析如下

方案一:从头到尾用两层循环比对字符,时间复杂度O(n²),不推荐

方案二:我想到了利用一个整形数组,下标对应字符的ASCII码,然后值存字符最新出现的数组位置。

这里我用len代表当前累计长度,i为字符在字符数组中的位置,tag为当前子串的起始位置。这样做只需对该字符数组进行一次遍历,时间复杂度为O(n)。

c语言解法如下

int lengthOfLongestSubstring(char * s){
    //常用字符ASCII码范围是0~128,开150的数组绰绰有余
    int tem[150]={0};
    int len = 0,i=1,result=0,tag=0;
    while(*s != '\0'){
        int a = s[0];
        if(tem[a]==NULL || tem[a]<tag){
            tem[a] = i; //标记该字符存在的最新位置
            len++;
        }else{
            result=len>result?len:result;
            tag=tem[a];
            len=i-tag-1;
            tem[a]=NULL;
            continue;
        }
        s++;
        i++;
    }
    return len>result?len:result;
}

最后提交结果如下,可以看到算法还可以继续进行优化:

执行用时:

4 ms, 在所有 C 提交中击败了84.91%的用户

内存消耗:

5.5 MB, 在所有 C 提交中击败了100.00%的用户

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

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

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档