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

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

滑动窗口
依次枚举子串的起始位置,那么子串的结束位置也是递增的。这里的原因在于,假设我们选择字符串中的第k个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为 rk。
那么当我们选择第k+1个字符作为起始位置时,首先从k+1 到 rk的字符显然是不重复的,并且由于少了原本的第k个字符,我们可以尝试继续增大rk,直到右侧出现了重复字符为止。

这样一来,我们可以使用滑动窗口来解决问题:

  • 我们使用两个指针来表示字符串的左右边界,左指针代表枚举子串的起始位置,可以不断地向右移动右指针,保证这两个指针所夹的子串没有重复字符,在移动结束后,这个子串就对应着以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度
  • 在枚举结束后,我们找到的最长的子串的长度即为答案

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

我们只要把队列的左边的元素移出就行了,直到满足题目要求!一直维持这样的队列,找出队列出现最长的长度时候,求出解!
时间复杂度:O(n)

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容