引言:用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)了,自然就不关心是否要继续判断:
代码:
/**
* @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;
};