通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 48. 最长不含重复字符的子字符串

97人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/890

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 48. 最长不含重复字符的子字符串

 

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

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

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

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

提示:

  • s.length <= 40000

难度:中等;标签:哈希表,双指针,滑动窗口;编程语言:C++


我的解法

class Solution {
public:
    // 想法:用辅助数组
    int lengthOfLongestSubstring(string s) {
        int aid[256], longest = 0, start = 0, len = s.length();
        fill(aid, aid+256, -1);

        for(int i = 0; i < len; i++){
            if(aid[s[i] - ' '] == -1){
                aid[s[i] - ' '] = i;
            }else{
                longest = max(longest, i - start);
                for(int j = start; j <= aid[s[i] - ' '] - 1; j++){
                    aid[s[j] - ' '] = -1;
                }
                start = max(start, aid[s[i] - ' '] + 1);
                aid[s[i] - ' '] = i;
            }
        }

        return max(longest, len - start);
    }
};

用一个数组记录字符第一次出现的位置,用start记录当前无重复字符的子串的开始位置,如果字符再次(第二次)出现,更新结果,同时更新start为字符第一次出现位置之后一个位置,这样该字符在当前子串中只出现一次


其它解法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int map[128]={0},len=0,start=0;
        for(int i=0;i<s.length();i++){
            ++map[s[i]];
            while(map[s[i]]==2){
                --map[s[start++]];
            }
            len = max(len,i-start+1);

        }
        return len;
    }
};

和我的解法方法是一样的,不过这里代码比较简短,同时也不是很好理解了,理解了我的解法再看这里就比较好理解了(方法是差不多一样的)


亲爱的读者:有时间可以点赞评论一下

点赞(1) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告