3-无重复字符的最长子串

LeetCode 3. Longest Substring Without Repeating Characters

LeetCode-3

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

method

滑动窗口，用一个集合存储出现过的元素

• 如果当前元素s[i]没在集合中，就更新res，然后把s[i]插入集合
• 如果已经存在，就弹出窗口最左边的元素，left往右移

int lengthOfLongestSubstring(string s) {
    unordered_set<char> st;
    int res = 0;
    int left = 0;
    for (int i = 0; i < s.size(); i++) {
        while (st.count(s[i])) {    // 这里要用while
            st.erase(s[left]);  // 弹出窗口左边元素
            left++; // 左端点右移
        }
        st.insert(s[i]);    // 插入集合 
        res = max(res, i - left + 1);   // 更新res，左闭右闭区间
    }
    return res;
}

也可以用数组代替set

int lengthOfLongestSubstring(string s) {
    int hash[256] = {0};
    int res = 0, left = 0;
    for (int i = 0; i < s.size(); i++) {
        while (hash[int(s[i])]) {
            hash[int(s[left])]--;
            left++;
        }
        hash[int(s[i])]++;
        res = max(res, i - left + 1);
    }
    return res;
}