LeetCode刷题日志#3:无重复字符的最长子串 - 滑动窗口法
文章目录
题目:传送门
类别:字符串
难度:中等
相关算法:滑动窗口法
思路
准备一个空数组做寄存数组。从左往右开始读字符串,准备一个一个字符往寄存数组里添加。
加之前要先判断下,如果寄存数组没有,那直接加就是;如果已经有了,那么从寄存数组里该字符位置的下一个位置截断寄存数组,构成新的寄存数组。
当然要记下原来寄存数组的长度,比较下,新的更长就更新。记当度就够了,题目只要长度,不要求字串是什么。当然要的也简单,记两个下标即可。
代码
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let largestLen = 0;
let uniqueArr = [];
for (let i = 0, len = s.length; i < len; i += 1) {
const currentChar = s[i];
const lastIndex = uniqueArr.indexOf(currentChar);
if (lastIndex > -1) {
uniqueArr = uniqueArr.slice(lastIndex + 1);
}
uniqueArr.push(currentChar);
const uniqueArrLen = uniqueArr.length;
if (uniqueArrLen > largestLen) {
largestLen = uniqueArrLen;
} else {
// 优化:提前结束
if (largestLen >= uniqueArrLen + len - i) {
return largestLen;
}
}
}
return largestLen;
};
思考
发现,如果 uniqueArr 改为字符串还会更快,内存消耗更小点。
还有,原来这个叫滑动窗口法?
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论