【算法题】无重复字符的最长子串
程序员文章站
2024-02-25 09:45:04
...
问题:
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例:
给定 "abcabcbb"
,没有重复字符的最长子串是 "abc"
,那么长度就是3。
给定 "bbbbb"
,最长的子串就是 "b"
,长度是1。
给定 "pwwkew"
,最长子串是 "wke"
,长度是3。请注意答案必须是一个子串,"pwke"
是 子序列 而不是子串。
思路:
首先要保存遍历到未重复的字符,这里可以用哈希表,当然python里可以用字典,C/C++可以用128位的数组标志ascii码中的128位字符。这道题主要就是考虑子串的起点和终点在哪里,起点不能简单地从重复字符开始算,因为重复字符之间肯定没有其他重复字符了,所以这里需要用两个标志标注子串的起点和终点,当重复了以后,则从上一个起点的下一个字符开始遍历。
代码:c/C++
#include <iostream>
#include <vector>
using namespace std;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
int lengthOfLongestSubstring(string s) {
int zimu[256] = {0};
int len = 0;
int max = len;
int n_iter = 0;
int pre = n_iter;
while( n_iter < s.size())//直到整个字符串都遍历完成
{
if(zimu[s[n_iter]] == 1)//如果当前的子串有该字符
{
if(max < len)//找到最大的长度
{
max =len;
}
for(int j = 0;j<256;j++)//清空标志位
{
zimu[j] = 0;
}
n_iter = pre +1;//从上一个起点的下一个字符开始
pre = n_iter;//更新起点为现在开始遍历的位置
zimu[s[n_iter]] =1;
len = 1;
}
else
{
len ++;if(len>max) max =len;//找到最大的长度
zimu[s[n_iter]] =1;
}
n_iter ++;
}
return max;
}
int main()
{
printf("%d\n",lengthOfLongestSubstring("dvdf"));
return 0;
}