Hi，大家好，我是Tom。一个美术生转到Java开发的程序员。今天给大家分享的是力扣题第3题，无重复的最长字符串。在解题过程中，也会手写一些伪代码。当然，如果想要完整的源码的话，可以到我的个人主页简介中获取。
这道题呢属于中等难度，评估为四颗星，它的通过率只有39%。
1、题干分析
首先，我们还是来分析一下这道题的题干。它说的是，给定一个字符串 s，让我们来找出不含重复字符的 最长子串 的长度。注意，这个地方不重复的最长子串是指它其中连续的字符串的部分。比如说，官方给了几个示例，我看第1个示例：
对于这道题，我给出两种解题方法。第一种方法是暴力法求解，第二种方法是滑动窗口求解。
2、暴力法求解
首先，我们来分析一下暴力法求解的思路。这个答案我们目测，最长不重复子串为 bacd ，它的长度为4。但是程序怎么才能判断出来呢？其实暴力法的逻辑分厂简单，就是字符串中的每个字符和后面的进行比较，一直累计不重复的次数，最后，将累计最大的值返回。
首先，我们定义一个方法叫 checkUnique(）,专门用来检测是否重复，如果重复就返回 fasle ，如果不重复就返回 true。
然后，我们用两个循环，依次比较，比如第一层循环游标为 i，第二层循环游标为 j。
第一轮比较的游标值为 i = 0，j = 1。首先拿 a 和 b 比较，发现不重复就累加，然后，a 和 c 比较发现不重复，继续累加。然后，a 和 b比较依次类推。
第一轮比较完成之后，进行第二轮比较，游标值 i = 1，j = 2, 也就是拿 b 和 c 比较，不重复累加，b 和 b 比较重复 不累加，然后b 和 a比较以此类推。
最后，依次比到第九轮，i = 8，j = 9，我们最终得到累计的最大值。
这是暴力法求解的伪代码：
当然，暴力求解法是最笨的方法，也是效率最低的办法，我不推荐使用。
3、滑动窗口求解
下面，给大家介绍一种更高效的解法，滑动窗口求解，也叫双指针求解，我们先来理解一下滑动窗口的解题思路。我们定义一个左指针 left 和右指针 right 进行实时地滑动，一般情况下这两个指针都是往右滑动。右指针最先开始滑动，只要满足条件就会一直往右滑动，当不满足条件的时候，左指针才开始往右滑动，直到能让右指针满足条件为止。那么，左指针和右指针之间的区间，我们就可以理解为滑动的窗口。当然，这个滑动的窗口可以是固定宽度，也可以是可变宽度。
假设有这样一个字符串 “ abcbacdca ”，下面我们利用滑动窗口的思想来快速找到这个字符串中不重复的最长子串。最开始的时候，我们把左指针和右指针同时指向这个字符串的首位置。同时，我们还定义一个 length 来记录当前遍历到的当前窗口的长度，默认赋值为字符串的长度为8。然后，定义 maxLength ，表示当前不重复子字符串的最大长度用于结果输出，默认为 0。然后，还要定义一个数组 window，用于标记窗口中的元素。这个数组的长度我固定为128，因为，一会我将要利用字符的 ASCII 码作为数组的索引下标，然后，在数组对应的下标位置坐标记。而 ASCII 码的 范围 0- 127，也就是128个值，正好覆盖到所有的字符。
首先是右指针就要开始往后移动。右指针每遍历到一个元素呢，它都要放入到 window 中，如果发现 window 中已经存在遍历过的元素，说明，左指针就要往后移动。
接下来，我们来模拟程序的执行逻辑。首先，左指针 和 右指针默认都指向 a 这个字符。
第一步，将右指针指向的 a 字符放入到 window 中，而 a 的 ASCII 码是 97，所以在下标为 97 的位置标记为 1，表示 a 出现的位置为 1。maxLength 加 1更新为1，同时,右指针往后移动。
第二步，将右指针指向的 b 字符放到入到 window 中，下标为 98 的位置，并且标记为 2，表示 b 出现的位置为 2。maxLength 加 1更新为2，同时,右指针继续往后移动。
第三步，将右指针指向的 c 字符放入到 window 中，下标为 99 的位置，并且标记为 3，表示 c 出现的位置为 3。maxLength 加 1更新为3，同时,右指针继续往后移动。
第四步，将右指针指向的 b 字符放入到 window 中，下标为 98 的位置，这个时候，发现 b 在前面出现过，所以，左指针要移动到 b 上一次出现的位置之后，也就是 c 的位置下标为 2。然后，再将下标为 98 的值更新为 b 出现的位置为 4，同时，右指针继续往后移动。
第五步，将右指针指向的 a 字符放入到window中，下标为 97 的位置，这个时候，我们又发现 a 在之前出现过，所以，左指针又要移动到 a 上次出现的位置之后，也就是 b 的位置下标为 1。然后，再将下标为 97 的值更新为 a 出现的位置为 5，同时，右指针继续往后移动。
第六步，将右指针指向的 c 字符放入到window中，下标为 99 的位置，这个时候，我们又发现 c 在之前出现过，所以，左指针又要移到 c 上次出现的位置之后，也就是 b 的位置，下标为 3。然后，再将下标为 99 的值更新为 c 出现的位置为 6，同时，右指针继续往后移动。
第七步，将右指针指向的 d 字符放入到 window中，下标为 100 的位置，d 在之前没有重复出现，所以将 99 的值标记为 d 出现的位置为7，左指针保持不动，maxLength 加 1 更新为 4，右指针继续往后移动。
第八步，将右指针指向的 c 字符放入到window中，下标为 99 的位置，这时我们又发现 c 在之前出现过，所以，左指针又要移到 c 上次出现的位置之后，就是 d 的位置，下标为 6。然后，再将下标为99的值更新为 c 出现的位置为 8，同时，右指针继续往后移动。
第九步，将右指针指向的 a 字符放入到windown中，下标为 97 的位置，这时我们发现 a 又在之前出现过，所以，左指针又要移动 a 上次出现的位置之后，也就是 c 的位置，下标为 5，然后，再将下标为 97 的值更新为 a出现的位置为9，同时，右指针继续往后移动。
这时候，右指针已经超出了字符串的范围，所以，最终maxLength的值顶格在 4。
这是滑动窗口求解的伪代码：
以上就是我对于无重复的最长字符串这道题的解题思路分享。只要是遇到字符串查找相关的问题，利用双指针有非常好的适用性。这道题除了滑动窗口求解以外，其实还可以使用动态规划等方法求解。如果需要完整代码的小伙伴，可以在我的个人主页简介中获取。
我是被编程耽误的文艺Tom，如果我的分享对你有帮助，请动动手指一键三连分享给更多的人。关注我，面试不再难！
