3. Longest Substring Without Repeating Characters

Leetcode link

解题思路

本题要求我们找到一个字符串的最长不重复子串的长度

因为子串的连续性，我们可以考虑滑动窗口的方式

具体而言，我们创建两个指针 left 和 right，分别作为窗口的两个边界

一开始，left 指向第一个元素，right 负责向右遍历，直到遇到了与窗口中重复的字符

记录下当前长度之后，我们就可以把 left 往右一个元素，然后继续遍历 right 了

最后，当 left 移到最后一个元素之后，我们比较一下记录下来的长度，取出最大值就好

查找字符是否重复我们可以用哈希集合的数据结构

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.size();
        int right = -1;
        int res = 0;
        unordered_set<char> occ;

        for(int left = 0;left < len;left++) {
            if(left != 0) {
                occ.erase(s[left - 1]);
            }

            while((right + 1 < len) && (occ.find(s[right + 1]) == occ.end())) {
                occ.insert(s[right + 1]);
                right++;
            }

            res = max(res, right - left + 1);
        }
        return res;
    }
};

Javascript

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const set = new Set()
    let left = 0
    let right = 0
    let res = 0

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

    return res
};