无重复字符的最长子串——滑动窗口

一、滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

用两个指针维护一个连续区间：

left → [无重复字符] ← right

right 不断向右扩展窗口。

遇到重复字符，就移动 left，直到窗口重新满足“无重复”。

---

二、核心思路

例如：

abcabcbb

窗口：

[a b c]

继续加入 a：

[a b c a]

出现重复。

记录每个字符上一次出现的位置：

lastindex[c]

发现重复后，直接：

left = lastindex[c] + 1;

让 left 跳过上一次出现的字符。

---

三、代码

int lengthOfLongestSubstring(char* s)
{
    int left = 0;
    int right = 0;
    int lastindex[128];
    int max_len = 0;

    memset(lastindex, -1, sizeof(lastindex));

    while (s[right])
    {
        char c = s[right];

        if (lastindex[c] >= left)
        {
            left = lastindex[c] + 1;
        }

        lastindex[c] = right;

        int len = right - left + 1;

        if (len > max_len)
        {
            max_len = len;
        }

        right++;
    }

    return max_len;
}

四、最核心的三句话

right：扩大窗口
left：处理重复
lastindex：记录字符上次的位置

重复时：

left = lastindex[c] + 1;

这就是滑动窗口。