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
查看原帖
点赞 评论
相关推荐
投递滴滴等公司7个岗位 > 点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
华为一面43人在聊 牛客热帖
正在热议
# 牛客帮帮团来啦！有问必答 #
710268次浏览 11527人参与
# 许愿池 #
77183次浏览 1541人参与
# 通信硬件人笔面经互助 #
107736次浏览 2178人参与
# 你的秋招进展怎么样了 #
500852次浏览 13424人参与
# 找工作时遇到的神仙HR #
177651次浏览 1744人参与
# 如何写一份好简历 #
259292次浏览 3918人参与
# 铜五铁六真的存在吗？ #
27339次浏览 293人参与
# 找工作，你会甘心进小厂还是猛冲大厂 #
35044次浏览 352人参与
# 产品实习，你更倾向大公司or小公司 #
35949次浏览 548人参与
# 非技术岗是怎么找实习的 #
73859次浏览 1385人参与
# 市场营销面经 #
4544次浏览 125人参与
# 互联网公司评价 #
79553次浏览 1087人参与
# 通信硬件薪资爆料 #
196302次浏览 1759人参与
# 你的秋招进行到哪一步了 #
352975次浏览 6269人参与
# 硬件兄弟们 甩出你的华为奖状 #
27511次浏览 180人参与
# 无实习如何秋招上岸 #
224675次浏览 3518人参与
# 投了多少份简历才上岸 #
56655次浏览 947人参与
# 面试中的破防瞬间 #
82563次浏览 1015人参与
# 通信/硬件的薪资开多少，才值得去？ #
10739次浏览 140人参与
# 产品人求职现状 #
50586次浏览 747人参与