给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
滑动窗口
依次枚举子串的起始位置,那么子串的结束位置也是递增的。这里的原因在于,假设我们选择字符串中的第k个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为 rk。
那么当我们选择第k+1个字符作为起始位置时,首先从k+1 到 rk的字符显然是不重复的,并且由于少了原本的第k个字符,我们可以尝试继续增大rk,直到右侧出现了重复字符为止。
这样一来,我们可以使用滑动窗口来解决问题:
- 我们使用两个指针来表示字符串的左右边界,左指针代表枚举子串的起始位置,可以不断地向右移动右指针,保证这两个指针所夹的子串没有重复字符,在移动结束后,这个子串就对应着以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度
- 在枚举结束后,我们找到的最长的子串的长度即为答案
滑动窗口其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!
如何移动?
我们只要把队列的左边的元素移出就行了,直到满足题目要求!一直维持这样的队列,找出队列出现最长的长度时候,求出解!
时间复杂度:O(n)