题目：
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
-
自行解答：
int lengthOfLongestSubstring(string s) {
int length = s.length();
string result = "";
int resultlength = 0;
string s2 ;
for(int i = 0;i<length;i++){
int stripos = result.find(s[i]);
s2 = s[i] ;
//2.1 确认子char在目标字符串中是否存在，存在就更新目标子字符串
if(stripos >=0){
result = result.substr(stripos+1,result.size()-1);
}
//2.2 插入新的子char
result = result.insert(result.size(), s2);
//2.3 比较当前目标子串的长度，更新最大值 resultlength
if(resultlength < result.length()){
resultlength = result.length();
}
}
cout << "result :" <<result<<endl;
return resultlength;
}
思路：（滑动窗口法）
1:遍历字符串
2：目标子串，在遍历过程确认符合条件的子串
2.1 确认是否存在子串的过程中，每次循环开始将新的子char和目标比较，存在需要将目标子串更新成 从目标子串中出现和新的子char的位置+1 到 新的子char的位置 新目标子串，遍历继续
2.2 若遍历过程中新子串不在目标子串中，则将新出现的子串插入到目标子串中
2.3 每次编译完成一个子串，则检查一下目标子串的长度，若长度增大，则更新目标子串的长度
3：输出子串长度
复杂度分析
-
时间复杂度：O(string.lenth()),即O(N)
-
空间复杂度：O(3N) ，主要是引入了额外2个变量result 和s2 存储字符串，在最差的情况下将达到 3 *s.length,即O（3N）
-
官方解答：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
思路：
- 使用unordered_set 存储String对应的每一个位置上的char，使用了unordered_set的set集合特性
- 双层循环，外层循环卡住左指针，内层循环移动右指针，内层循环退出的条件：
- 移动到string最后一位；
- 出现重复元素
- 比较左右指针都移动结束后寻找到的不重复子串的长度，每次内外循环结束，更新
复杂度分析
- 时间复杂度：O(N)O(N)，其中 NN 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
- 空间复杂度：O(|\Sigma|)O(∣Σ∣)，其中 \SigmaΣ 表示字符集（即字符串中可以出现的字符），|\Sigma|∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0, 128)[0,128) 内的字符，即 |\Sigma| = 128∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 |\Sigma|∣Σ∣ 个，因此空间复杂度为 O(|\Sigma|)O(∣Σ∣)
网友评论