用c语言求一个子字符串中最长并且没有重复字符的子串
时间: 2024-03-20 11:44:51 浏览: 21
以下是用C语言实现求一个子字符串中最长且没有重复字符的子串的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int lengthOfLongestSubstring(char *s) {
int len = strlen(s);
int max_len = 0;
int start = 0;
int end = 0;
int letter_map[128] = {0}; // 存储字符出现的次数,ASCII码最多只有128个
while (end < len) {
if (letter_map[s[end]] == 0) { // 当前字符没有出现过
letter_map[s[end]] = 1; // 将字符出现次数标记为1
end++; // 串的右端点右移
max_len = (max_len > end - start) ? max_len : end - start; // 更新最长子串长度
} else { // 当前字符出现过
letter_map[s[start]] = 0; // 将左端点对应的字符出现次数标记为0
start++; // 串的左端点右移
}
}
return max_len;
}
int main() {
char *s = "abcabcbb";
int max_len = lengthOfLongestSubstring(s);
printf("Max length of substring: %d\n", max_len);
return 0;
}
```
这里采用了滑动窗口的思想,即用两个指针 start 和 end 分别表示当前子串的左端点和右端点,用 letter_map 数组记录每个字符出现的次数。当一个字符第一次出现时,将其出现次数标记为1,并将右端点向右移动;当一个字符出现次数大于1时,将其出现次数标记为0,并将左端点向右移动。在遍历整个字符串的过程中,不断更新最长子串的长度 max_len。