第 5 题常用的是：

中心扩展双指针

也就是：从某个中心开始，left 向左走，right 向右走。所以它不是“相向双指针”，而是中心扩展
2. 前提条件

第 5 题要找：最长回文子串

回文串就是：正着读和反着读一样。

例如：

"aba"
"abba"
"bb"

都是回文。

不是回文：

"abc"
"abca"

3. 核心概念：回文有中心
每一个回文串都有中心。

但是中心有两种情况。

情况一：奇数长度回文

例如："aba"

中心是：'b'

形式：

left = i
right = i
情况二：偶数长度回文

例如：

"abba"

中心在两个字符中间：

'b' 和 'b' 中间

形式：

left = i
right = i + 1

所以每个位置都要尝试两种中心：

1. 以 i 为中心
2. 以 i 和 i+1 中间为中心
4. 中心扩展模板
while (left >= 0 && right < n && s[left] == s[right]) {
    left--;
    right++;
}

循环结束时，说明越界了，或者左右字符不相等了。
此时left已经减去了1和right已经加上了1，所以回调回去就行
此时真正的回文范围是：

[left + 1, right - 1]
right-1-(left+1)+1=right-lift-1
长度是：right - left - 1
因为循环最后一次失败时，left 和 right 已经多走了一步。

5. 第 5 题 C 语言题解

LeetCode 第 5 题返回 char*，所以需要 malloc 一个答案字符串。

#include <stdlib.h>
#include <string.h>

int expand(char* s, int n, int left, int right) {
    while (left >= 0 && right < n && s[left] == s[right]) {
        left--;
        right++;
    }
//这里就是从0开始往右边遍历寻找那个回文中心
    return right - left - 1;
}

char* longestPalindrome(char* s) {
    int n = strlen(s);

    int start = 0;
    int maxLen = 1;

    for (int i = 0; i < n; i++) {
        int len1 = expand(s, n, i, i);
        int len2 = expand(s, n, i, i + 1);
//len1是奇中心的算法，len2是偶中心的算法
        int len;
        if (len1 > len2) {
            len = len1;
        } else {
            len = len2;
        }

        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
//之后两者比较算出最大的len之后，计算起始start位置
    char* ans = malloc((maxLen + 1) * sizeof(char));

    for (int i = 0; i < maxLen; i++) {
        ans[i] = s[start + i];
    }

    ans[maxLen] = '\0';

    return ans;
}
6. start = i - (len - 1) / 2 怎么来的？

这个公式用来根据中心 i 和回文长度 len 求起点。

奇数回文时
例如：

s = "babad"
中心 i = 1，对应 'a'
回文 = "bab"
len = 3

起点：
i - (len - 1) / 2
= 1 - (3 - 1) / 2
= 1 - 1
= 0

所以从 0 开始。

偶数回文时
例如：

s = "cbbd"
中心 i = 1 和 i+1 = 2
回文 = "bb"
len = 2

起点：

i - (len - 1) / 2
= 1 - (2 - 1) / 2
= 1 - 0
= 1

所以从 1 开始。

这个公式同时适用于奇数和偶数。

7. 第 5 题易错点
易错点 1：只考虑奇数回文

如果只写：expand(s, n, i, i);

就会漏掉：

"bb"
"abba"

所以必须还要写：expand(s, n, i, i + 1);

易错点 2：循环结束后范围多走了一步

中心扩展结束时：
left 和 right 已经不属于回文范围。

真正范围是：

left + 1 到 right - 1

长度是：

right - left - 1
易错点 3：返回字符串要补 '\0'
常识需要知道
C 语言字符串必须以 '\0' 结尾。

所以：

ans[maxLen] = '\0';


8. 第 5 题复杂度

中心扩展法：

时间复杂度：O(n^2)
空间复杂度：O(1)

如果算返回字符串空间，就是：O(n)

9. 题型总结
第 5 题可以用双指针，但不是普通相向双指针。

普通相向双指针：
    left 从头开始
    right 从尾开始
    两边往中间走

最长回文子串：
    从中心开始
    left 向左走
    right 向右走
    两边向外扩展

第 5 题的双指针是“中心扩展”，核心是枚举中心，然后向两边扩展。