题解 | #最长不含重复字符的子字符串#

最长不含重复字符的子字符串

http://www.nowcoder.com/practice/48d2ff79b8564c40a50fa79f9d5fa9c7

C语言求解 最长不含重复字符的子字符串

解题思路

不妨先假设有一个字符串 abcdbddefa,正常的遍历角度进行分析,从前往后,依次遍历,关键在于如何判断重复字符,以及发现重复字符后的操作。判断之前是否存在重复字符使用 hash表的思想,我先定义两个数组,遍历的时候用一个数组存放元素下标,另一个flag数组用于标识该元素已存放到数组。 因此正常遍历abcd 会分别在两个数组的相同位置存入下表和标识。当遍历到b,会先从flag数组中查看是否已经存在,如果存在说明已经找到了一条新的长度,判断当前的长度和记录最值的长度大小。然后将遍历的下标移动到前一个重复字符的下一个位置,并且重置一下flag数组杰克,也就是原来遍历到后一个b,此时移动到前一个b的后一位 c的位置 继续遍历即可。

 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
int max_num(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
int lengthOfLongestSubstring(char* s ) {
    if(s==NULL)
        return 0;
    if(strlen(s)==1)
        return 1;
    int hash[200];//hash表 用于存放位置
    int flag[200]={0};//flag 用于标识是否已存在
    int len=strlen(s);
    int maxlength=0,templength=0;
    for(int i=0;i<len;i++){
        //说明该位置之前已存在
        if(flag[s[i]]==1)
        {
            //取最大值
            maxlength=max_num(maxlength,templength);
            //长度清空
            templength=0;
            memset(flag,0,200*sizeof(int));
            //hash表flag清零
            i=hash[s[i]]+1;
        }
        //先将位置存入hash表
        hash[s[i]]=i;
        flag[s[i]]=1;
        templength++;
        
    }
    maxlength=max_num(maxlength,templength);
    return maxlength;
}
全部评论

相关推荐

八极星:我看成了化身一团黑子哈哈哈😂
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务