题目描述
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3 Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
题目意思就是， 给一个字符串， 找到字符串中， 没有重复字符的最长的子串的长度
分析
最容易想到的， 依然是暴力遍历， 用两层for循环遍历字符串s中的每一个子串，再对每个子串循环遍历计算不重复的长度， 这样有三层遍历的关系，时间复杂度O(n ^ 3)
显然这样太慢了， 反复检查每一个字符串其实是有冗余操作的，不必要检查每一段子串，因为如果下标从 i 到 j 都是不重复的元素， 我们只要检查 第 j+1个元素是否存在于下标 i — j之间就可以了。
可以用两个指针 left, i 指向字符串第一位， 然后遍历循环 i， 如果字符串中下标为 i 的值不在hash表中， 则说明当前字符没出现过，当前长度 cL 加1， 反之，如果在hash表中有下标为 i 的值， 说明之前该字符已出现过， 则我们要滑动检查字符串的左边界 left， 将它滑动到当前位置，更新检查的范围。
我的Javascript解法
/**
* @param {string}
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let l = s.length
// 先过滤掉边界情况
if (l <= 1) { return l }
let hash = {}
// 滑动窗口(遍历检查字符串)的左边界
let left = 0
// 当前长度
let cL = 0
// 最终确定的最长长度
let fL = 0
for (let i =0; i < l; i++) {
let t = s[i]
// 如果当前hash表中，出现了当前字符， 说明之前出现过
if (hash[t] >= left) {
// 更新左边界为hash表中之前存的字符位置
left = hash[t]
// 根据当前下标，左边界下标， 计算长度
cL = i - left
} else {
// 没有出现在hash表中， 说明之前没出现过该字符， 长度加一
cL++
}
// 把当前字符的位置， 储存在hash表中记录下来
hash[t] = i
// 如果当前的长度比最大长度还大， 则更新最大长度为当前长度
if (cL > fL) {
fL = cL
}
}
return fL
};
As a follower of @followforupvotes this post has been randomly selected and upvoted! Enjoy your upvote and have a great day!
This post has received a 3.13 % upvote from @drotto thanks to: @hughie8.
You got a 10.00% upvote from @upvoteturtle. Thank you very much for using this upvote service. 😍
We would be very happy about a delegation to grow and increase the maximum upvote!😉
10SP 20SP 50SP 100SP 200SP
This voting Bot pays 100% out to all Delegators and gives an upvote Revenue of 120%