Leetcode是许多欧美IT公司招聘工程师经常使用的算法题库，学习算法最重要的是不断积累.

今天我们来看一道 链表linkedlist相关的题目

LeetCode Q3: Longest Substring Without Repeating Characters问题描述：

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", which the length is 3.

Example 2:

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

给出一个字符串s,我们要去找到一个substring子字符串,这个子串不包含重复字符，并且是最长的。

问题分析：

-1. 这是一个字符串中可能包含大小写字符或者其他字符

-2.怎么找到符合条件的最长的字串：双循环？还是滑动窗口？

-3.怎么保存下来最长字串的长度？

解决方案：

Solution 1: 使用两层循环的方式固定i,然后j=i+1开始往右扫描判断是可以的，但是复杂度是O(N^2)。

Solution 2: 使用滑动窗口的方法，维护两个指针L和R分别指向窗口的左右边界，复杂度是O(N)

1.初始化L=R=0,最左开始扫描

2.定义一个哈希表，借助额外空间来存储滑动窗口中的字符，和对应的下标

3.循环扫描，R开始右移。循环退出条件是：R到s末尾并且L<=R

4.If 当前字符在哈希表中不存在，则说明是新字符，假如哈希表并右移R进入下次循环 | 或者当前出现的字符已经在滑动窗口的左边界外，则更新当前的字符index;

----比如 s="abba";

Else, 说明找到滑动窗口中已经存在一个字符和当前字符相同。 这时我们需要计算当前的substring长度并对比Max len赋值,同时 L移动到当前出口中重复字符的下一个位置作为新的左边界，然后更新字符的index位R。

R++，进入下一次循环

5。最后R可能扫描到了末尾都没有重复字符，所以我们需要在循环结束后重新计算下最长子串长度，然后 return.

Java:

Python:

AC 52ms 运行结果：

m=distinct char numbers

时间复杂度O(n),空间复杂度O(m)

总结：

这是一道简单题，然是有很多细节的地方会阻止你写出“简单易读”且“无逻辑错误”的代码。

本题有两个corner case需要注意：

注意字符串中重复字符的替换和index更新不要忘记退出循环后仍人要比较一次 max和(R-L)

关注，转发和收藏“松鼠游学”，每日更新 "Leetcode" 算法相关的面试题和解题方案并附上源码，欢迎有兴趣的小伙伴私信私聊！

@极限尤可突破，至臻亦不可止!