题目1:给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
时间: 2024-03-01 22:43:45 浏览: 37
给定一个字符串 s ,要找出其中不含有重复字符的最长子串的长度,可以使用滑动窗口的方法来解决。滑动窗口是指在一个字符串或数组上维护一个窗口,通过移动窗口的起始位置和结束位置来寻找目标子串。
具体的步骤如下:
1. 创建一个空的集合(用来检测字符是否重复)和两个指针,分别指向子串的起始位置和结束位置。
2. 将结束位置的字符添加到集合中。
3. 如果集合中已经存在当前字符,则移动起始位置的指针,并从集合中删除起始位置的字符,直到集合中不再存在当前字符。
4. 更新最长子串的长度(结束位置 - 起始位置 + 1)。
5. 将结束位置的指针向右移动一位,并将新字符添加到集合中。
6. 重复步骤2到5,直到结束位置达到字符串的末尾。
下面是使用滑动窗口方法的Python代码实现:
```python
def lengthOfLongestSubstring(s):
if not s:
return 0
charset = set()
start = 0
max_len = 0
for end in range(len(s)):
while s[end] in charset:
charset.remove(s[start])
start += 1
charset.add(s[end])
max_len = max(max_len, end - start + 1)
return max_len
```
相关问题
给定一个字符串 s,请你找出其中不含有重复字符的 最长子串 的长度
给定一个字符串 s,我们需要找出其中不含有重复字符的最长子串的长度。可以使用滑动窗口的方法来解决这个问题。
滑动窗口是一种常用的解决子串或子数组问题的方法。它通过维护一个窗口,来遍历整个字符串。具体步骤如下:
1. 定义两个指针,left 和 right,分别表示窗口的左边界和右边界。
2. 初始化最长子串的长度为 0,定义一个集合 set 来存储窗口中的字符。
3. 遍历字符串 s,不断移动右指针 right,并将对应的字符加入到集合 set 中。
4. 如果集合 set 中已经存在当前字符,表示出现了重复字符,需要移动左指针 left,并将对应的字符从集合 set 中移除,直到集合 set 中不再包含重复字符。
5. 在每次移动左指针 left 和右指针 right 后,更新最长子串的长度为 max(maxLength, right - left + 1)。
6. 重复步骤 3-5,直到遍历完整个字符串 s。
最终得到的 maxLength 就是不含有重复字符的最长子串的长度。
给定一个字符串,请你找出其中不含有重复字符的最长子串的长度
题目描述:
给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题思路:
使用滑动窗口的思想,维护一个窗口,窗口内的元素不重复,每次移动右边界,如果右边界的元素在窗口内出现过,则移动左边界,直到窗口内不再有重复元素。
代码实现:
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)