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，解题结束；

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

欢迎关注华为云博客：程序员欣宸

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