【算法题】无重复字符的最长子串

﹏ヽ暗。殇╰゛Y 2022-05-25 07:54 117阅读 0赞

**问题：**

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

给定 `"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;
    }