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) {
    let right = -1;
    let res = 0;
    let len = s.length;
    let occ = new Set();
    for(let left = 0;left < len;left++) {
        if(left !== 0) {
            occ.delete(s[left - 1]);
        }

        while(right + 1 < len && !occ.has(s[right + 1])) {
            occ.add(s[right + 1]);
            right++;
        }

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

    return res;
};