字节跳动面试题
发布时间
阅读量：
阅读量
题目描述：给定长度为m的字符串aim,以及1个长度为n的字符串str，问能否在str中找到1个长度为m的连续子串，使得这个子串刚好由aim的m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1
public int strStr(String str, String aim) {
if(aim.length() > str.length()) return -1;
//将其转为数组
char[] chars = str.toCharArray();
char[] chara = aim.toCharArray();
int[] count = new int[256];
int r = 0;
int m = aim.length();
int inVaildTimes = 0; //记录无效点数
for(int i = 0; i < m; i++){
count[chara[i]]++; //定义欠债表
}
//先对str中等长的子串进行操作
for(; r < m; r++){
if(count[chars[r]]-- <= 0){
inVaildTimes++; //当还没有减之前就小于0了 inVaildTimes++
}
}
//跳出来时 r = m 如果无效点数为0 则找到
for(; r < chars.length; r++){
if(inVaildTimes == 0){
return r - m;
}
if(count[chars[r]]-- <= 0){
inVaildTimes++;
}
//滑动窗口 去除最左边的那个
if(count[chars[r - m]]++ < 0){
inVaildTimes--;
}
}
return inVaildTimes == 0 ? r - m : -1;
}全部评论 (0)
还没有任何评论哟~