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

无重复字符的最长字串

作者头像
小飞侠xp
发布2018-08-27 17:55:35
6400
发布2018-08-27 17:55:35
举报

LeetCode 3. Longest Substring Without Repeating Characters 已知一个字符串,求用该字符串的无重复字符组成的最长子串的长度。 例如: s = "abcabcbb" -> "abc", 3 s = "bbbbb" -> "b", 1 s = "pwwkew" -> "wke", 3 注意 "pwke"是子序列而非子串。

算法设计

利用滑动窗口 双指针维护滑动窗口,整个过程中,使用begin与i维护一个窗口,该窗口中的子串满足题目 条件(无重复的字符),窗口线性向前滑动,整体时间复杂度为O(n)。 1.设置一个记录字符数量的字符哈希,char_map; 2.设置一个记录当前满足条件的最长子串变量word; 3.设置最长满足条件的子串的长度result; 4.设置两个指针(记作指针i与指针begin)指向字符串第一个字符; 5.i指针向后逐个扫描字符串中的字符,在这个过程中,使用char_map记录字符数量 如果word中没出现过该字符:对word尾部添加字符并检查result是否需要更新; 否则:begin指针向前移动,更新char_map中的字符数量,直到字符s[i]的数量为1;更新word,将 word赋值为begin与i之间的子串。

代码语言:javascript
复制
class Solution{
public:
    int lengthOfLongestSubstring(std::string s){
        int begin = 0;
        int i = 0;//滑动窗口指针
        std::string word = "";
        int char_map[128] = {0};
        for(int i = 0; i < s.length(); i++){
            char_map[s[i]]++;
            if(char_map(s[i]) ==1){
                word + =s[i];
                if( result < word.length()){
                    result = word.length()
                }
            }
            else{
                while(begin < i && char_map[s[i]] > 1){
                    char_map[s[begin]]--;
                    begin ++;
                }
                word = "";
                for(int j = begin; j < =i; j++){
                    word += s[j];
                }
            }  
        }
        return result;
     }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.05.10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

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