【JS攻略Leetcode】No.3. Longest Subs

引言：用Js攻略leetcode中的算法，将会介绍自己的思路和注意点，一边学习一边愉快刷题呀。

问题：

给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。

思考:

采用动态的划窗来查找无重复子串，用noRepeatHead指示当前划窗的起始位置，noRepeatEnd指示当前划窗的下一个需要验证的元素,当前不重复的字符组成的划窗子串为initialString。
初始时：

查找noRepeatEnd对应的元素是否在initialString中存在，若不存在，划窗自动加上这个元素，然后变成下面的状态：

若元素已经存在，直接截取从重复元素到当前元素的字符串，保持整个字符串中字符不重复。
(因为之后的字符串可能更长，比如‘abcbedg’, 原先的initialString为abc, 第四个字符‘b’在initialString中，直接截取‘cb’，再往后判断，因为往后可能有子串比目前的最大长度3还要大，例如‘cbedg’的长度5)
因为截取后长度肯定不大于之前noRepeatHead和noRepeatEnd之间的长度，所以直接不判断temp（当前initialString的长度）和返回值（nowMaxLength）的大小

直到noRepeatHead到达字符串末尾结束（下图 noRepeatEnd == s.length 了）：

或者从noRepeatHead到字符串末尾的长度已经不能超过当前的最大长度（nowMaxLength）了，自然就不关心是否要继续判断：

noRepeatHead = 5, s.length = 8, nowMaxLength = 3， 所以最后三个就不用判断啦

代码：

/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
    var result = 0;
    if(s.length <= 1) {
        return s.length;
    }
    var nowMaxLength = 1, noRepeatHead = 0, noRepeatEnd = 1;
    var initialString = s[0]; var temp = 1, index = -1;
    do {
           index = initialString.indexOf(s[noRepeatEnd]);
           if(index == -1) {
                temp++;
                if(temp>nowMaxLength){
                    nowMaxLength  = temp;
                }
                initialString  +=  s[noRepeatEnd];
                noRepeatEnd ++;
            } else {
                noRepeatHead = noRepeatHead+ index + 1;//重复的话就把头移到重复元素的下一个元素上；
                noRepeatEnd ++;
                initialString = s.substring(noRepeatHead, noRepeatEnd);
                temp = initialString.length;
            }
      }while(noRepeatHead < (s.length - nowMaxLength) && (noRepeatEnd < s.length));
      return nowMaxLength;
};