searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

无重复字符的最长子串-算法学习

2023-07-13 06:05:53
2
0

题目详情:
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例:
输入: s = "abcabcbb"
输出: 3 

解题思路:

使用两个指针 leftright 来构建滑动窗口。开始时,窗口的左边界和右边界都指向字符串的第一个字符。

然后,我们不断移动右边界,并将对应的字符加入到集合 set 中。如果碰到字符已经存在于集合中,说明出现了重复字符,此时我们需要移动左边界,并从集合中删除对应的字符,直到窗口中不再有重复字符。

在每次移动窗口时,我们更新最长不重复子串的长度 maxLength,并将其与当前窗口的长度 (即 right - left + 1) 进行比较,取较大值。

最后,函数返回最长不重复子串的长度。


代码实现:

function lengthOfLongestSubstring(s) {
    let maxLength = 0; // 最长不重复子串的长度
    let left = 0; // 滑动窗口的左边界
    let right = 0; // 滑动窗口的右边界
    const set = new Set(); // 用于存储当前窗口中的字符集合

    while (right < s.length) {
        if (!set.has(s[right])) {
            set.add(s[right]);
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        } else {
            set.delete(s[left]);
            left++;
        }
    }

    return maxLength;
}

// 示例输入
const s = "abcabcbb";

// 调用函数获取最长不重复子串的长度
const result = lengthOfLongestSubstring(s);

// 输出结果
console.log(result);
0条评论
作者已关闭评论
t****m
98文章数
1粉丝数
t****m
98 文章 | 1 粉丝
t****m
98文章数
1粉丝数
t****m
98 文章 | 1 粉丝
原创

无重复字符的最长子串-算法学习

2023-07-13 06:05:53
2
0

题目详情:
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例:
输入: s = "abcabcbb"
输出: 3 

解题思路:

使用两个指针 leftright 来构建滑动窗口。开始时,窗口的左边界和右边界都指向字符串的第一个字符。

然后,我们不断移动右边界,并将对应的字符加入到集合 set 中。如果碰到字符已经存在于集合中,说明出现了重复字符,此时我们需要移动左边界,并从集合中删除对应的字符,直到窗口中不再有重复字符。

在每次移动窗口时,我们更新最长不重复子串的长度 maxLength,并将其与当前窗口的长度 (即 right - left + 1) 进行比较,取较大值。

最后,函数返回最长不重复子串的长度。


代码实现:

function lengthOfLongestSubstring(s) {
    let maxLength = 0; // 最长不重复子串的长度
    let left = 0; // 滑动窗口的左边界
    let right = 0; // 滑动窗口的右边界
    const set = new Set(); // 用于存储当前窗口中的字符集合

    while (right < s.length) {
        if (!set.has(s[right])) {
            set.add(s[right]);
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        } else {
            set.delete(s[left]);
            left++;
        }
    }

    return maxLength;
}

// 示例输入
const s = "abcabcbb";

// 调用函数获取最长不重复子串的长度
const result = lengthOfLongestSubstring(s);

// 输出结果
console.log(result);
文章来自个人专栏
js
57 文章 | 1 订阅
0条评论
作者已关闭评论
作者已关闭评论
0
0