leetcode 3. 无重复字符的最长子串
题目
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
题解
我们要求解子串的长度,可以分为以下部分
- 找到无重复的子串
- 获取该长度
- 获取最大长度
滑动窗口,双下标检测
使用下标begin和end来构建子字符串,子字符串[begin,end)左闭右开,这样子我们可以直接使用s[end]来判断该字符是否存在于子字符串[begin,end)中.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if (n == 1 || n == 0) return n;// 处理简要情况
// [begin,end),初始子串默认包含了s[0]
int begin = 0;
int end = 1;
int maxLength = 1;
int length = 1;
while (end < n) {
char endChar = s[end]; // 获取要判断的元素
for (int i = begin; i < end; i++) {
if (endChar == s[i]) { // 检查是否在子串中
begin = i + 1; // 更新begin,移动到i+1位置
length = end - begin; // 更新子串长度
break;
}
}
end++; // end移动到下一位置
length++; // 将刚刚的endChar加入到子串中
if (maxLength < length) maxLength = length; // 判断长度
}
return maxLength;
}
};
