当前位置:网站首页>力扣题(3)—— 无重复字符的最长子串
力扣题(3)—— 无重复字符的最长子串
2022-07-30 22:06:00 【世界的隐喻】
无重复字符的最长子串
题目内容
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-substring-without-repeating-characters
题解一:双循环暴力解法
因为要考虑双循环的边界问题,会比较麻烦。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
res = []
ans = 0
if len(s) <=1: # 考虑循环边界问题,当长度为 0 或 1 时,并不会进入双循环但此时无重复字符的最长子串就是本身的长度
return len(s)
for i in range(0, len(s)-1):
res.append(s[i])
for j in range(i+1, len(s)):
if s[j] in res and res.index(s[j]) == 0:
res.pop(0) # 因为是子串,所以去除的重复字符一定要是该子串的第一个字符,不然就不构成子串,即需要退出第二层循环
elif s[j] in res and res.index(s[j]) != 0:
res = []
flag = 0 # 判断第二层循环是否是正常结束,如果第二层循环已经循环到最后一个字符,那么就不要在进行任何循环,因为接下来找到的子串长度都不是最长的
break
res.append(s[j])
ans = max(ans, len(res))
flag = 1 # 判断是第二层循环正常结束
ans = max(ans, len(res))
res = []
if flag == 1:break
return ans
力扣通过的时间是196 ms
题解二:双循环暴力解法
这种双循环不用考虑边界问题,所以同时也就没有判断第二层循环是否是正常结束的条件,换言之就是耗时会比较长。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
res = ""
ans = 0
for i in range(0, len(s)):
while i < len(s):
if s[i] in res:
break
res += s[i]
i += 1
ans = max(ans, len(res))
res = ""
return ans
力扣通过的时间是564 ms。
题解三:滑动窗口(双指针?)
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left, right = 0, 0 # 左指针和右指针的初始位置
length = len(s)
res = []
ans = 0
while right < length:
if s[right] not in res: # 如果没有重复的字符出现,那么右指针往右移动
res.append(s[right])
right += 1
else: # 如果有重复字符出现,那么移动左指针直到左指针指向的字符和右指针指向的字符之间没有重复字符
res.pop(0)
left += 1
ans = max(ans, len(res))
return ans
边栏推荐
猜你喜欢
MYSQL JDBC Book Management System
MySQL 游标
How strict Typescript strict mode?
Navicat new database
The reason for not using bs4 is that the name is too long?Crawl lottery lottery information
宁波中宁典当转让29.5%股权为283.38万元,2021年所有者权益为968.75万元
It is enough for MySQL to have this article (disgusting typing 37k words, just for Bojun!!!)
MySQL cursors
代码越写越乱?那是因为你没用责任链
数据质量提升
随机推荐
c语言进阶篇:指针(五)
MySQL 8.0.29 设置和修改默认密码
TransGAN code reproduction - Jiutian Bisheng Platform
ThinkPHP高仿蓝奏云网盘系统源码/对接易支付系统程序
NEOVIM下载安装与配置
【Nacos】解决Nacos下载速度缓慢的问题
QT开发简介、命名规范、signal&slot信号槽
正则表达式语法及使用
for...in 和 for...of 的区别
cmd (command line) to operate or connect to the mysql database, and to create databases and tables
2022/07/30 学习笔记 (day20) 面试题积累
About the data synchronization delay of MySQL master-slave replication
不用bs4的原因居然是名字太长?爬取彩票开奖信息
How do I refresh the company's background management system (Part 1) - performance optimization
navicat无法连接mysql超详细处理方法
史上超强最常用SQL语句大全
The mysql time field is set to the current time by default
Knowledge of C language corners of byte alignment
Day 16 of HCIP
cookie和session区别