本题我最开始的想法就是使用双指针与滑动窗口,滑动过程中维护一个集合,集合内保存滑动窗口内部的所有字符,右边的指针每指向一个新的元素,就判断该元素(字符)是否在集合内,如果已经存在,就说明此时将要出现重复字符,以及无重复字符的子串已经达到了最长的长度,之后我们需要移动左边的指针,直到集合内不存在重复字符,进入下一个循环。
为什么这种方法是正确的?这个题目最直接的想法应该是:从左往右遍历每个元素,尝试以该元素起始的无重复字符的子串的长度。假设以下标l
的元素开始的最长子串的右边元素下标为r
,说明下一个下标为r + 1
的元素在[l, r]
的子串中已经存在了,此时我们如果再向右移动左侧指针一个位置,将右侧指针重置为左侧指针旁边一个位置,然后重新开始尝试,已经没有意义了,因为新子串的中间一部分我们之前已经尝试过了。我们可以直接固定右侧指针,移动左侧指针直到没有重复元素,以此时的位置作为起点开始尝试,这样减少了一部分尝试次数。
// C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
if (len == 0 || len == 1) {
return len;
}
int l = 0, r = 0;
unordered_set<char> st;
int res = 0;
while (r < len) {
while (r < len && st.find(s[r]) == st.end()) {
st.insert(s[r]);
r++;
}
int cnt = r - l;
res = res > cnt ? res : cnt;
if (r >= len) {
break;
}
while (l < r && st.find(s[r]) != st.end()) {
st.erase(s[l]);
l++;
}
}
return res;
}
};
// Java
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len == 0 || len == 1) {
return len;
}
int l = 0, r = 0;
Set<Character> set = new HashSet<>();
int res = 0;
while (r < len) {
while (r < len && set.contains(s.charAt(r)) == false) {
set.add(s.charAt(r));
r++;
}
int cnt = r - l;
res = res > cnt ? res : cnt;
if (r >= len) {
break;
}
while (l < r && set.contains(s.charAt(r)) == true) {
set.remove(s.charAt(l));
l++;
}
}
return res;
}
}
当然,我们永远需要注意,字符串(数组)的下标不要越界。
标签:子串,int,res,len,st,Hot,100,LeetCode,指针 From: https://www.cnblogs.com/louistang0524/p/18413778