LeetCode 第三题 (Longest Substring Without Repeating Characters) 三部曲之一：解题思路

欢迎访问我的 GitHub

这里分类和汇总了欣宸的全部原创(含配套源码)：https://github.com/zq2599/blog_demos

• 笔者在完成 LeetCode 第三题(Longest Substring Without Repeating Characters)时，经历了设计、实现、优化三个阶段，于是通过这个三部曲系列，将当初的整个过程重现，希望有兴趣的读者来一起讨论；

三部曲完整链接

1. 《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之一：解题思路》;

2. 《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二：编码实现》;

3. 《LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之三：两次优化》;

• 先来看下优化后的最终效果，如下图，编程语言是 Java，17 毫秒完成，超越 99.94%的提交方案：

  
  
  

• 上述成绩的地址是：https://leetcode.com/submissions/detail/199426736/

三部曲说明

• 整个系列由三篇文章组成：

• 第一篇，也就是本文，描述基本解题思路；

• 第二篇，根据解题思路完成初版的代码实现，目标是保证功能正常，能在 LeetCode 网站提交成功；

• 第三篇，针对初版代码做了两轮优化，每轮都有一个优化的重点，最终将耗时从 40ms 以上优化到 17ms；

题目简介

1. 题目地址是：https://leetcode.com/problems/longest-substring-without-repeating-characters/

2. 题目内容：输入一个字符串例如"abcabcbb"，找到最长的不重复的字符串的长度返回，这里应该返回的是"abc"的长度 3；

解题思路简述

• 该题的关键是设计一个"滑动窗口"，里面存的是最长的不重复字符串，一开始这个窗口是空的，如下图，绿色代表滑动窗口，蓝色的是外部输入的字符串：

• 

• 从字符串的第一个元素开始，执行这个逻辑：

1. 用一个变量保存当前已经发现的最大长度，假设名为 maxLen；

2. 如果当前检查的元素在窗口中没有，就加入窗口，例如窗口中已经有了"ab"，当前是"c"，那么窗口中最大长度加一；

3. 如果当前检查的元素在窗口中存在，例如窗口中已经有了"abc"，当前检查的元素是"a"，这个"a"在窗口总已经存在了，窗口作调整，窗口中的"a"和它左侧的所有元素全部移除窗口，再把当前检查的"a"元素加入窗口；

4. 拿当前窗口的长度和 maxLen 比较，大的值存入 maxLen 中；

5. 继续检查字符串的下一个元素，逻辑是前面的步骤；

思路详细图解

• 以前面的"abcabcbb"为例，来把上述逻辑用图片演示一遍；

• 检查完第一个元素后，窗口效果如下图，可见第一个元素已经纳入窗口中：

  
  
  

• 检查完第三个元素后，效果如下图，maxLen 等于 3，三个元素纳入窗口：

  
  
  

• 检查到第四个元素是"a"，那么窗口的左侧和右侧都开始滑动，maxLen 等于 3，当前窗口中的长度也是 3，因此 maxLen 不变,如下图：

  
  
  

• 继续检查第 5 个元素，这次遇到的"b"在窗口中也存在，处理如下图：

  
  
  

• 继续检查第 6 个元素，这次遇到的"c"在窗口中也存在，所以第一个"c"移出窗口，第二个"c"加入窗口，窗口内的元素还是 3 个，所以 maxLen 保持不变，处理如下图：

  
  
  

• 检查第 7 个元素"b"，窗口中已经有"b"了，所以左侧窗口向右收缩，将里面原有的中的"b"移出，右侧窗口向右扩张，将第 7 个元素"b"纳入窗口中，此时窗口中元素数量为 2，小于 maxLen，所以 maxLen 不变，如下图：

  
  
  

• 检查第 8 个元素"b",发现窗口中已经有"b"了，只能将窗口中的"b"(第 7 个元素)和它左侧的"c"(第 6 个元素)都从窗口中移出，再把第 8 个元素纳入窗口，此时窗口中只有一个元素，因此 maxLen 不变，如下图：

  
  
  

• 数组已经遍历完毕，返回 maxLen=3，解题结束；

• 以上就是解题思路，用代码来实现整个思路并不难，下一篇文章我们来看下基本的代码实现；

欢迎关注 InfoQ：程序员欣宸

学习路上，你不孤单，欣宸原创一路相伴...