高端大气的网站制作,如何给网站配色,8718企业服务平台,国企网站开发问题描述
输入#xff1a;一个字符串 s。输出#xff1a;最长的无重复字符的子串的长度。
示例 输入: s abcabcbb 输出: 3 解释: 最长的无重复字符的子串是 abc#xff0c;长度为 3。 输入: s bbbbb 输出: 1 解释: 最长的无重复字…问题描述
输入一个字符串 s。输出最长的无重复字符的子串的长度。
示例 输入: s abcabcbb 输出: 3 解释: 最长的无重复字符的子串是 abc长度为 3。 输入: s bbbbb 输出: 1 解释: 最长的无重复字符的子串是 b长度为 1。 输入: s pwwkew 输出: 3 解释: 最长的无重复字符的子串是 wke长度为 3。
约束条件
0 s.length 5 * 10^4字符串 s 可以包含英文字符、数字、符号和空格。
解决方案
我们可以使用滑动窗口的方法来解决这个问题。滑动窗口是一种常用的算法技巧用于处理数组或字符串中的子区间问题。具体步骤如下 通过这种方法我们可以高效地找到最长的无重复字符子串时间复杂度为 O(n)其中 n 是字符串 s 的长度。空间复杂度为 O(min(n, m))其中 m 是字符集的大小对于 ASCII 字符集m 为 128。
使用两个指针 left 和 right 来表示当前窗口的左右边界。使用一个哈希集合Set来存储当前窗口内的字符以便快速检查字符是否重复。移动 right 指针扩展窗口直到遇到重复字符。当遇到重复字符时移动 left 指针收缩窗口直到窗口内没有重复字符。在每次移动 right 指针时更新最长子串的长度。 function lengthOfLongestSubstring(s) {let left 0;let right 0;let maxLength 0;const charSet new Set();while (right s.length) {if (!charSet.has(s[right])) {// 如果当前字符不在集合中将其加入集合charSet.add(s[right]);// 更新最长子串的长度maxLength Math.max(maxLength, right - left 1);// 移动右指针right;} else {// 如果当前字符在集合中移除左指针指向的字符charSet.delete(s[left]);// 移动左指针left;}}return maxLength;
}// 示例用法
console.log(lengthOfLongestSubstring(abcabcbb)); // 输出: 3
console.log(lengthOfLongestSubstring(bbbbb)); // 输出: 1
console.log(lengthOfLongestSubstring(pwwkew)); // 输出: 3 详细解释 初始化变量 left 和 right 分别表示滑动窗口的左右边界初始值都为 0。maxLength 用于记录最长无重复字符子串的长度初始值为 0。charSet 是一个集合用于存储当前窗口内的字符。 滑动窗口 使用 while 循环遍历字符串 s直到 right 指针到达字符串末尾。如果当前字符 s[right] 不在 charSet 中 将该字符加入 charSet。更新 maxLength 为当前窗口的长度 right - left 1。移动 right 指针。如果当前字符 s[right] 已经在 charSet 中 从 charSet 中移除 s[left]。移动 left 指针。 返回结果 返回 maxLength 作为最长无重复字符子串的长度。
