最长不重复子串

请从字符串中找出一个最长的不包含重复字符的子字符串，并计算该最长子字符串的长度。

示例

  1. 输入: "abcabcbb"
  2. 输出: 3 
  3. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  5. 输入: "bbbbb"
  6. 输出: 1
  7. 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
  9. 输入: "pwwkew"
  10. 输出: 3
  11. 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
  12.      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题

1.滑动窗口，哈希表

1.判空
2.初始化：窗口的开始值，窗口长度，最大子串的开始值，长度，哈希表
3.循环：
判断当前位置字符
<1> 在哈希表中：同时字符在窗口范围内，则更新滑动窗口的起始值和长度。
<2> 不在哈希表中：滑动窗口长度++。如果窗口长度>当前最大子串长度，更新最大子串的开始值，长度
当前位置字符放入哈希表，重复则覆盖
4.根据最大子串的开始值和长度返回子串，并且此时长度就是最大子串的长度

这种解法的重点是求出最长不重复子串，顺便求出子串长度。

  1. class Solution {
  2.     /**
  3.        滑动窗口，哈希表
  4.      */
  5.     public int lengthOfLongestSubstring(String s) {
  6.         if(s == null || s.length() == 0)  return 0;
  8.         int start = 0,  len = 0;
  9.         int startindex = 0,  maxlen = 0;
  11.         String result="";
  12.         Map<Character,Integer> map = new HashMap<>();
  14.         for(int i = 0; i < s.length(); i++){
  15.             char ch = s.charAt(i);
  16.             Integer value = map.get(ch);
  17.             if(value != null && value >= start){ //保证窗口中都是不重复的子串
  18.                 start = value + 1;
  19.                 len = i - value;
  20.             }else{ //不在哈希表 或者 哈希表中已经存在但是在窗口外面 
  21.                 len++;
  22.                 if(len > maxlen){
  23.                     maxlen = len;
  24.                     startindex = start;
  25.                 }
  26.             }
  27.             map.put(ch,i);
  28.         }
  29.         result = s.substring(startindex,(startindex + maxlen));
  30.         return maxlen;
  31.     }
  33. }