js实现 给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
要实现给定一个字符串 s ,找出其中不含有重复字符的最长子串的长度,可以使用滑动窗口的方法。
具体步骤如下:
- 创建一个空的集合 set 来存储已经遍历过的字符。
- 创建两个指针 left 和 right,分别表示当前子串的左右边界。
- 初始化最长子串的长度为 0 和当前子串的长度为 0。
- 从左到右遍历字符串 s,遍历过程中执行以下操作:
- 如果当前字符 s[right] 不在集合 set 中,说明当前字符可以加入到当前子串中,将该字符加入集合 set,并更新当前子串的长度。
- 如果当前字符 s[right] 在集合 set 中,说明当前字符重复了,需要从当前子串中移除所有重复字符,移除的过程中更新集合 set 和当前子串的长度。
- 更新最长子串的长度为当前子串的长度和最长子串的长度中的较大值。
- 返回最长子串的长度。
以下是使用 JavaScript 实现的代码:
function lengthOfLongestSubstring(s) {
const set = new Set();
let left = 0, right = 0;
let maxLen = 0, currLen = 0;
while (right < s.length) {
if (!set.has(s[right])) {
set.add(s[right]);
currLen++;
maxLen = Math.max(maxLen, currLen);
right++;
} else {
set.delete(s[left]);
left++;
currLen--;
}
}
return maxLen;
}
// 示例
console.log(lengthOfLongestSubstring("abcabcbb")); // 输出 3,对应的最长子串为 "abc"
console.log(lengthOfLongestSubstring("bbbbb")); // 输出 1,对应的最长子串为 "b"
console.log(lengthOfLongestSubstring("pwwkew")); // 输出 3,对应的最长子串为 "wke"
该算法的时间复杂度是 O(n),其中 n 是字符串 s 的长度
原文地址: https://www.cveoy.top/t/topic/iHId 著作权归作者所有。请勿转载和采集!