子串题库

2024年04月09日

柏拉文

越努力，越幸运

一、无重复字符的最长子串

---

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

1.1 滑动窗口

思路

1. 我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界

2. 在每一步的操作中，我们会将左指针向右移动一格, 表示我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

   • 判断是否为重复字符串: JavaScript 中的 Set , 在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符

3. 在枚举结束后,我们找到的最长的子串的长度即为答案

实现

function lengthOfLongestSubstring(s){
    const set = new Set();
    const length = s.length;
    let rk = -1;
    let result = 0;
    for(let i=0; i<length; i++){
        if(i !== 0){
            set.delete(s[i-1]);
        }
        while(rk+1<length && !set.has(s[rk+1])){
            set.add(s[rk+1]);
            rk++;
        }
        result = Math.max(result,rk-i+1);
    }
    return result;
}

• 时间复杂度: O(N)