1. 题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1：
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2：
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3：
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
示例 4:
2. 算法思路
使用滑动窗口，记录下最大的窗口大小。
pos数组表示该字符上一次出现的位置，初始化为-1。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int pos[256]; memset(pos, -1, 1024);
int left = 0, right = 0, max_len = 0;
while (right < s.length()) {
left = max(left, pos[s[right]] + 1);
max_len = max(max_len, right - left + 1);
pos[s[right++]] = right;
}
return max_len;
}
};
|
算法复杂度
- 时间复杂度：仅一次循环遍历数组，复杂度为。
- 空间复杂度：
