【LeetCode】T43 1~n整数中1出现的次数

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

aab 、"alouzxilkaxkufsu"(leetcode 有栈溢出情况)

思路:快慢指针,慢指针停留,快指针往前,并往 map 里面记录字符的次数(只要没重复的就往前)。若出现重复则低指针到高指针位置,清空 map。整个过程更新最大值。

  • 维护一个map{a, 1},数字代表出现次数;max 为最大长度,t 为每轮的长度
  • 快慢指针hl, 快指针往前,用s[h]的值在 map 里面查
    • 没有重复就前进,在 map 中标记s[h],更新maxt
    • 有重复,慢指针l 移到 h处,h前进,更新maxt;清空 map

奈何长度过长时,会出现缓冲区溢出的情况,本地测试通过。

int lengthOfLongestSubstring(string s) {
    if(s.length() == 0)
        return 0;
    
    map<int, int> _map;
    int low = 0;
    int high = 0;
    int t = 0;
    int max = 0;
    while(low < s.size() && high < s.size()){
        if(_map[s[high]] == 0){
            if(s[high] == s[high -1]) // aab的情况
                t = 1;
            else
                t++;
            max = t > max ? t : max;
            _map[s[high]] = 1;
            high++;
        } else {
            max = t > max ? t : max;
            t = (s[high] == s[high -1]) ? 1 : 0; // aab的情况
            low = high;
            high++;
            _map.clear();
        }
    }
    return max;
}

最后借鉴了评论区的思路,不用记录每一轮的 t,用高低指针之差算长度。后面调试过程发现应该是由_map.clear();引起的,还是循环的过程中 _map[s[low]]--

int lengthOfLongestSubstring(string s) {
    if(s.length() == 0)
        return 0;

    map<int, int> _map;
    int low = 0;
    int high = 0;
    int max = 0;
    while(high < s.size()){
        if(_map[s[high]] == 0){
            _map[s[high]]++;
            high++;
            max = max > (high - low) ? max : (high - low);
        } else {
            max = max > (high - low) ? max : (high - low);
            _map[s[low]]--;
            low++;
        }
    }
    return max;
}

本文链接:https://ariser.cn/index.php/archives/393/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!