TrionFordring
2022-04-11 14:30 门头沟学院 Java
关注
我觉得可以用双指针ij。大概思路就是逐渐增大ij之间的窗口大小，当大小等于p时就匹配成功了。
每次迭代，j指针指向下一个字符，当下一个字符数量已经超出时，向右移动i至当前字符值的下一个位置。
时间复杂度O(n).
输入：
t=CABABBABC
p=ABBC
迭代(左右括号代表ij):
- []CABABBABC
- [C]ABABBABC
- [CA]BABBABC
- [CAB]ABBABC
- CA[BA]BBABC // 此处A的数量已经超出，所以i移动到了第一个A后面
- CA[BAB]BABC
- CAB[ABB]ABC// 此处B的数量已经超出，所以i移动到了第一个B后面
- CABA[BBA]BC
- CABAB[BAB]C
- CABAB[BABC] // ij之间距离==4,return
查看原帖
点赞 评论
相关推荐
Momenta公司福利 452人发布 点赞 评论 收藏
分享
点赞 评论 收藏
分享
02-24 14:18
北京邮电大学 Java 
AAA不喝拿铁：校友好，开投就完事了！要准备面试的话更建议刷codetop，hot100有些题并不是面试常考题。另外想看刷题路线的可以看我的帖子，有讲怎么刷leetcode，除此之外可以看看我根据真实面经整理得到的最全（高/中/低频）面试题，加油
点赞 评论 收藏
分享
查看9道真题和解析 牛客热帖
更多
正在热议
更多
# 实习进度记录 #
154542次浏览 1724人参与
# 我的求职精神状态 #
2951次浏览 79人参与
# 平安产险科技中心求职汇总 #
244494次浏览 2613人参与
# 京东美团大战，你怎么看？ #
21286次浏览 191人参与
# 好未来求职进展汇总 #
6037次浏览 46人参与
# 大家每天通勤多久？ #
30982次浏览 229人参与
# Keep实习校招 #
48923次浏览 252人参与
# 大城市找工作会更容易吗 #
16429次浏览 125人参与
# 金山WPS工作体验 #
20789次浏览 133人参与
# 提前批过来人的忠告 #
97677次浏览 1092人参与
# 签约有哪些注意事项 #
27093次浏览 227人参与
# 招银网络科技工作体验 #
18829次浏览 85人参与
# 生化环材还是天坑吗 #
30036次浏览 277人参与
# 4399求职进展汇总 #
17528次浏览 139人参与
# 中兴求职进展汇总 #
579607次浏览 2614人参与
# 华为存储OD事变 #
121679次浏览 681人参与
# 京东工作体验 #
12535次浏览 88人参与
# 生物制药/化工校招攻略 #
39968次浏览 275人参与
# 校招第一份工作你干了多久？ #
66755次浏览 334人参与
# 腾讯音乐求职进展汇总 #
82136次浏览 450人参与
# 小红书求职进展汇总 #
49627次浏览 441人参与
# 宁德时代求职进展汇总 #
104946次浏览 622人参与