【LeetCode 训练营 3，5】无重复字符的最长子串+最长回文子串

• 💌 博客内容：LeetCode 训练营 

• 😀 作  者：陈大大陈

• 🚀 个人简介：一个正在努力学技术的准前端，专注基础和实战分享 ，欢迎私信！

• 💖 欢迎大家：这里是CSDN，我总结知识和写笔记的地方，喜欢的话请三连，有问题请私信 😘 😘 😘

目录

3. 无重复字符的最长子串

我的思路 

源码 

5. 最长回文子串

我的思路

源码 

后记

3. 无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104

s 由英文字母、数字、符号和空格组成

我的思路 

• 这道题目我们采用双指针写法，定义一个left变量指向最长子串的首字母，定义right来从首字母往后遍历字符串。 
• 设置两个遍历，第一个遍历用来遍历字符串，并将same置为0，第二个遍历用来遍历无重复字符的子串，当有重复字符时将same置为1,并让left+1。
• 遍历完一次子串后，更新子串长度max的信息。
• 让right++继续判断。

源码 

int lengthOfLongestSubstring(char * s){
    int i,j,max=0;
    int left=0,right=0,same=0;
    int len=strlen(s);
  for(i=0;i<len;i++)
  {
            same=0;
        for(j=left;j<right;j++)
        {
            if(s[j]==s[right])
            {
                same=1;
                break;
            }
        }
        if(same==1)
        {
            left=j+1;
        }
        max=max>(right-left+1)?max:(right-left+1);
        right++;
  }
    return max;
}

 成功过关。

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

我的思路

• 这道题目我是采用中心扩散的方法，遍历每个字符（这个字符可能是一个，也可能是两个，一个就像aba，两个就像abba）来找它周围的回文子串.
• 从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就继续扩展,如果两边的字母不同，我们就停止扩展，因为在这之后的子串都不能是回文串了。
• 我们要找出最长的那个,所以要记得更新子串长度max。

源码 

void extend(char*s,int left,int right,int*end,int*start)
{
   if(left<0||right>=strlen(s))
   {
       return;//越界就直接结束
   }
    while(left>=0&&right<strlen(s)&&s[left]==s[right])
    {
        left--;
        right++;//是回文子串时就循环
    }
   
    if(right-left-1>(*end))
    {
        *end=right-left-1;//更新最大子串的长度
        *start=left+1;
    }
  
    return;
}
char * longestPalindrome(char * s){
int i,j; 
int *start=(int*)malloc(sizeof(int));
    *start=0;
    int *end=(int *)malloc(sizeof(int));
    *end=0;
for(i=0;i<strlen(s);i++)
{ 
    extend(s,i,i,end,start);
    extend(s,i,i+1,end,start);
   
}
 s[*start+*end]='\0';//从回文子串开始输出

   return s+*start;//输出到回文子串结束为止
}

成功过关。 

后记

我的方法时间复杂度和空间复杂度可能比较高，如果大佬们有更好的方法，请在下面评论区不吝赐教，私信我就更好了，我们一起进步！