YunheWang0813
10/26/2019 - 3:45 AM

0003. Longest Substring Without Repeating Characters

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0, r = 0, res = 0;
        vector<int> f(256, 0);
        while (l < s.size()) {
            if (r < s.size() && f[s[r]] == 0) {
                f[s[r++]]++;
            }
            else {
                f[s[l++]]--;
            }
            res = max(res, r - l);
        }
        return res;
    }
};

算法

用什么:Sliding Window

为什么:通过slide的相距来update result,所以用SW

解题

思路:先开一个f(256)和l,r两个pointer。while循环,在f[s[r]] == 0(没有记录)时,r往右移且记录对应字母(f[s[r]]); 有记录时,l往右移且删去对应字母(f[s[l++]]--)

注意之处:

  1. r < s.size() && f[s[r]] == 0 r < s.size()不能忘记

  2. for loop不能以i来循环,要以l判断

  3. 每次都要更新res

复杂度

时间:O(N)

空间:O(N)

类似的题