Leetcode之Longest Substring Without Repeating Characters 问题

问题描述：

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

示例：

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", 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

问题来源：Longest Substring Without Repeating Characters (详细地址：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/)

思路分析：

      在这我就不介绍复杂的解题思路了。介绍一种简便一点的方法，在这涉及到重复数字，所以我们可以采用Map来映射，key我们可以取每个字符，但是value应该取啥呢？结果求的是啥？最终的长度有多长，所以我们就用value来标记每个数字的索引不就完了？另外，我们在这采用两个指针，其中一个i用来遍历数组中的每个字符，另一个start用来标记每个不重复字符串的第一个字符。下面看看它们是怎么移动的？每遍历到一个字符的时候(i肯定得向右移)，我们就在hashmap中查找，看看它里面有没有出现过该字符，如果有，我们就得改变start的值了，需要让它指向上一次出现该重复字符串的右边一个字符，可能有点绕了，下面我们举个例子看看：

       就拿第一个字符串"abcabcbb"，刚开始start = 0,i = 0;当i向右遍历的时候，直到"c"，我们都没有碰到重复的字符串，所以现在的start仍然等于0，接下来i到了“a”，第一次碰到了重复的字符，所以我们就要移动start了，将start移动到上一次“a”出现的右边的一个索引(即start = 1)。当然，我们必须要保证start是要向右移动的，我们看看字符串“abbba”，

字符串：a    b     b     a  

               i   :  0    1    2     3          

     start ： 0    0    2     1     

有没有发现不对的地方？当遍历到第二个a的时候，start又回去了，所以我们在这为了保证start是向前走的，我们采用下面的表达式：

start = Integer.max(start, map.get(s.charAt(i)) + 1);

最后我们所求的字符串末端指向i，左边界指向start，所以字符串的总长度为i - start + 1。

代码：