# 题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例一🌰
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例二🌰
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例三🌰
输入: "dvdf"
输出: 3
解释: 因为无重复字符的最长子串是 "vdf"，所以其长度为 3。
# 解题思路
- 需要考虑到每一个字符串的所有组合形式,且每个组合形式中不能有相同的字符串;
- 可以定义一个变量
leftIndex来记录每一次重复的位置 - 利用
for循环遍历数组
# coding
# 解法一
将字符串转换为数组,然后查找:
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if (typeof s !== 'string' || s.length <= 0) return 0;
let charts = s.split('') // 字符串转数组
let maxLength = 0
let leftIndex = 0 // 记录每一次重复的位置
for (let start = 0; start < charts.length; start++) {
for (let i = leftIndex; i < start; i++) {
if (charts[i] == charts[start]) { // 若是有相同的字符串
maxLength = Math.max(maxLength, start - leftIndex)
leftIndex = i + 1 // 更新重复位置的下标
break // 跳出本次循环
}
}
}
return Math.max(maxLength, charts.length - leftIndex)
};
执行耗时116ms,内存消耗36.7MB.
# 解法二
使用下标来维护滑动窗口
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if (typeof s !== 'string' || s.length <= 0) return 0;
var start = 0,
maxLength = 0,
leftIndex = 0;
for (let j = 0; j < s.length; j++) {
leftIndex = s.slice(start, j).indexOf(s[j])
if (leftIndex == -1) {
maxLength = Math.max(maxLength, j - start + 1)
} else {
start += leftIndex + 1
}
}
return maxLength;
};
执行耗时92ms,内存消耗37.8MB.
测试代码
lengthOfLongestSubstring('abcabcbd')
// 3
阅读全文
