要查找一個字符串中非重復子串的個數,可以使用一個哈希表來記錄每個字符最后出現的位置,然后使用滑動窗口的方法來遍歷整個字符串。
具體步驟如下:
下面是使用C語言實現的代碼示例:
#include <stdio.h>
int nonRepeatSubstringCount(char* s) {
int lastPos[128]; // 記錄每個字符最后出現的位置
int i, j, count;
for (i = 0; i < 128; i++) {
lastPos[i] = -1;
}
i = 0;
j = 0;
count = 0;
while (s[j] != '\0') {
if (lastPos[s[j]] >= i) {
i = lastPos[s[j]] + 1;
}
lastPos[s[j]] = j;
count += j - i + 1;
j++;
}
return count;
}
int main() {
char str[] = "abcabcbb";
int count = nonRepeatSubstringCount(str);
printf("Non-repeating substring count: %d\n", count);
return 0;
}
以上代碼示例中,非重復子串的個數為9,分別為"abc", “bca”, “cab”, “abc”, “bc”, “b”, “ca”, “ab”, “abc”。