首页 > 其他 > 详细

新增5 最长不含重复字符的子字符串

时间:2018-03-20 23:48:00      阅读:232      评论:0      收藏:0      [点我收藏+]

请从字符串中找出一个最长不含重复字符的子字符串,计算该最长子字符串的长度。例如字符串“arabcacfr”中,最长不含重复字符的子字符串是“acfr”,长度为4。

思路:cur当前最长,max全局最长;hash数组记录字符对应下标;遍历字符串,如果字符对应hash值小于0,说明字符未出现,cur直接+1即可;如果大于等于0出现了说明重复字符,那就需要判断,如果两次出现长度差d大于cur说明重复字符不在当前cur长的字符串中,无需在意,cur+1即可,如果d小等于cur,说明重复字符在当前cur长的字符串汇中,需要重新计算最长长度,找规律可得cur = d。注意更新max。

 

int longestSubStringWithoutDuplication(const string &str)
{
    if (str.size() == 0) {
        return 0;
    }
    //历史最长,当前最长
    int max = 0, cur = 0;
    vector hash(26, -1);
    //遍历每一个字符
    for (int i = 0; i < str.size(); i++) {
        int preidx = hash[str[i] - a];
        //之前为存储过或者重复字符距离大于当前最长未重复距离,则cur++;
        if (preidx < 0 || i - preidx > cur) {
            cur++;
        }
        //存储过,且在重复
        else {
            cur = i - preidx; //(i-1) - preidx + 1;
        }
        //存储字符对应的下标索引
        hash[str[i] - a] = i;

        if (cur > max) {
            max = cur;
        }
    }
    return max;
}

 

新增5 最长不含重复字符的子字符串

原文:https://www.cnblogs.com/dingxiaoqiang/p/8613537.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!