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++]]--)
注意之处:
r < s.size() && f[s[r]] == 0
r < s.size()不能忘记
for loop不能以i来循环,要以l判断
每次都要更新res
时间:O(N)
空间:O(N)