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
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
很奥的前端仔：如果你接了offer 临时又说不去 hr确实要多做一些工作。 当然如果是接offer之前当我没说
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
- 1... 杂记近期所面试的三家中小厂9523
- 2... 工作半年后更确定：我们依然不欠优绩主义什么8571
- 3... 岁末论道：谁才是牛客 2025 最强修仙者?6844
- 4... #牛客2025仙途报告#居然是五颗星5117
- 5... 选择即命运—2025年度总结4696
- 6... 仙途报告4260
- 7... 圣诞节用 AI 做个牛客运营翻翻乐！(含代码)4232
- 8... 一个程序员的自救书｜从酒吧陪玩DM到上岸大厂3647
- 9... 互联网实习求职的黑话和timeline，你所需要知道的……3571
- 10... 大学废物离开优绩主义之后发现外面根本没下雨3174
正在热议
更多
# 牛客2025仙途报告 #
5476次浏览 147人参与
# 礼物开箱Plog #
1858次浏览 89人参与
# 2025年终总结 #
179333次浏览 3054人参与
# 工作两年，想和老板谈涨薪怎么说 #
38828次浏览 175人参与
# 哪些行业值得去? #
14408次浏览 77人参与
# 你面试体验感最差/最好的公司 #
23273次浏览 389人参与
# 秋招落幕，你是He or Be #
16485次浏览 304人参与
# 一人说一个提前实习的好处 #
15052次浏览 247人参与
# 今年你最想重开的一场面试是？ #
6372次浏览 89人参与
# 考公VS就业，你怎么选？ #
88164次浏览 497人参与
# 职场新人体验 #
156974次浏览 1123人参与
# 离家近房租贵VS离家远但房租低，怎么选 #
13742次浏览 130人参与
# 重来一次，你会对开始求职的自己说 #
7214次浏览 193人参与
# 找工作，行业重要还是岗位重要？ #
85904次浏览 1701人参与
# 各大公司公布25年Q3财报，你怎么看？ #
5063次浏览 50人参与
# 实习没事做是福还是祸？ #
19277次浏览 292人参与
# 机械制造秋招总结 #
97395次浏览 878人参与
# 宁德时代求职进展汇总 #
154197次浏览 686人参与
# 反问环节如何提问 #
126475次浏览 2670人参与
# 工作中听到最受打击的一句话 #
8837次浏览 152人参与