题解 | #长度为 K 的重复字符子串#
长度为 K 的重复字符子串
http://www.nowcoder.com/practice/eced9a8a4b6c42b79c95ae5625e1d5fd
-
长度为n的字符串有n-k个长度为k的子串,那么就遍历这n-k个子串看其中有没有重复的字母,只要有就计数,开始查看下一子串。
-
怎么判断是否有重复字母呢?因为字符串中全是小写字母,那么就用一个长度为26的数组来记录26个小写字母出现的次数。
-
每遍历一个子串,就把其中的字母出现次数记下,遍历完后再遍历计数数组,只要发现一个大于1的说明该字母重复,该子串是要找的子串。
int numKLenSubstrRepeats(char* s, int k ) {
int n = strlen(s);
int i = 0, j= 0, cnt = 0;
while(i<=n-k){ //n-k是最后一个长度为k的子串的起始下标
int arr[26] = {0}; //每次遍历子串之前都要把计数数组清零
int p = i; //p表示该趟从哪个下标开始遍历
for(p; p<i+k; p++) //遍历字母个数为k个
arr[s[p]-'a']++; //字符串里的字母与字符‘a’的差值当作计数数组的下标,表示该字母的位序,a,b,c依次为第0,1,2个
for(j=0; j<26; j++){ //遍历计数数组
if(arr[j] > 1){ //若发现某个计数大于1
cnt++; //说明该子串是要找的,先计个数
break; //拜拜了您嘞,后面的不用看了,去查看下一个子串去了
}
}
i++; //下一个子串的起始下标
}
return cnt;
}