滑动窗口-高频-无重复字符的最长子串

2023-08-16  本文已影响0人  1哥

高频-滑动窗口-无重复字符的最长子串
基本思路:
数据结构:
(1)一个map
负责记录当前窗口的映射情况,
(2)两个指针:
一个p, 一个q, p<=q, 当前窗口的size = q - p +1;
一个指针q,不断扩展窗口, 检查*q 是否已经在map 中:
i. 是的则调整窗口p右移,且去除map 对应flag直至不在map 中;
ii. 不是的则继续右移q; 并更新max

int lengthOfLongestSubstring(char * s){
    char *p=s, *q=s;
    int map[256]={0};
    int max=0;
    while(p<=q && *q) {
        if(map[*q]) {
            map[*p]=0;
            p++;
        } else {
            int sz=q-p+1;
            if (sz > max)
                max=sz;
            map[*q]=1;
            q++;
        }
    }

    return max;
}
上一篇 下一篇

猜你喜欢

热点阅读