最长不含重复字符的子字符串-剑指48（数组-贪心算法-c）

短命女 2022-11-18 01:58 142阅读 0赞

问题描述：  
最长不重复子串就是从一个字符串中找到一个连续子串，该字串中任何两个字符都不能相同，且该字串的长度是最大的。  
输入：每个测试用例输入一行由小写英文字符组成的字符串，字符串的长度部大于10000  
输出：输出最大长度的不重复子串长度。

样例输入：absd  
样例输出：4  
样例输入：abba  
样例输出：2  
样例输入：abdffd  
样例输出：4

解法：  
该题适合采用贪心求解，贪心的思路：当出现重复的字符，在子串中寻找子串出现的位置，选择该位置之后的串作为子串，然后把该字符添加进去，继续从该字符后面的一个字符扫描，如果不出现重复的则将该字符加到子串中，然后重复上述步骤即可。

int lengthOfLongestSubstring(char* str){ 
         int max = 0;
         int len = 0;
         char sub_str[128] = { '\0'};
         for(int i = 0; str[i] != '\0'; i++)
         { 
              char* ptr;
              //如果该字符没有出现在子串中，则添加到子串
              if(!(ptr = strchr(sub_str, str[i])))
              { 
                   sub_str[max] = str[i];
                   max++;
              }
              else{ 
              	   //更新长度
                   if(max > len)
                   { 
                        len = max;
                   }
                   //将原子串中出现重复字符的位置之后的子串，赋值给原子串作为新的子串
                   strcpy(sub_str, ptr+1);
    			   //由于原来的子串中可能比如今的子串长，所以清空后面的字符
                   for(int j = strlen(sub_str); j < max; j++)
                   { 
                        sub_str[j] = '\0';
                   }
                   //计算当前子串的长度，将重复的这个字符放到最后面，子串长度+1
                   int num = strlen(sub_str);
                   sub_str[num] = str[i];
                   max = num + 1;
              }
         }
         //由于有两个条件判断，所以比较下，选择最大长度
         len = len > max? len : max;
         return len;
    }

Note

1.  strchr函数：

*  原型：char \* strchr(char \* str, char/int c);
 *  作用：在字符串str中寻找字符C第一次出现的位置，并返回其位置（地址指针），若失败则返回NULL；

--------------------

再记录一下双指针解题思路：

class Solution:
        def lengthOfLongestSubstring(self, s):
            charSet=set()
            n=len(s)
            if n<=1:
                return n
            maxLen=1
            i=0
            j=0
            while(i<n and j<n):
                # 如果集合中不存在当前字符
                if s[j] not in charSet:
                    charSet.add(s[j])
                    j+=1
                    maxLen = max(j - i, maxLen)
                else:
                    charSet.remove(s[i])
                    i+=1
            return maxLen

c语言解题的话，创建一个队列用来存放子串就可以了.

参考：https://blog.csdn.net/qq\_37174526/article/details/81283888