题目描述

给你一个整数数组 nums。

如果数组 nums 的一个分割满足以下条件，我们称它是一个 美丽 分割：

1. 数组 nums 分为三段 非空子数组：nums1，nums2 和 nums3，三个数组 nums1，nums2 和 nums3 按顺序连接可以得到 nums。
2. 子数组 nums1 是子数组 nums2 的前缀 或者 nums2 是 nums3 的前缀。

请你返回满足以上条件的分割 数目。

子数组 指的是一个数组里一段连续 非空 的元素。

前缀 指的是一个数组从头开始到中间某个元素结束的子数组。

样例

输入：nums = [1,1,2,1]

输出：2

解释：

美丽分割如下：

nums1 = [1]，nums2 = [1,2]，nums3 = [1]。
nums1 = [1]，nums2 = [1]，nums3 = [2,1]。

输入：nums = [1,2,3,4]

输出：0

解释：

没有美丽分割。

限制

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 50

算法1

(分类讨论，KMP) $O(n^2)$

1. 将 $nums1$ 是 $nums2$ 的前缀和 $nums2$ 是 $nums3$ 的前缀分开两种情况讨论，统计答案过程中去重。
2. 对于第一种情况，使用 KMP 算法求出 $nums$ 的 $next$ 数组。然后枚举一个偶数长度的位置 $i$，得到以 $i$ 为后缀时的最大相同前缀的结束位置 $j = next(i)$。如果 $j$ 没有达到 $[0, i)$ 的一半，则说明 $[0, i/2)$ 无法作为 $[i/2, i)$ 的前缀。如果 $j$ 达到了，但长度的一半不能被循环节的长度整除，则也无法作为前缀。当这两点都满足时，$nums1$ 可以取 $[0, i / 2)$，$nums2$ 可以取 $[i/2, k)$，$nums3$ 可以取 $[k, n)$。这里的 $k$ 只要大于 $i/2$ 即可。
3. 对于第二种情况，枚举 $nums2$ 的起始位置 $s$（此时固定下 $nums1$ 为 $[0, s)$），然后求 $[s, n)$ 的 $next$ 数组。按照和第一种情况同样的方式，找到某些位置，满足 $nums2$ 是 $nums3$ 的前缀。
4. 需要使用一个哈希表去重两种情况可能产生的相同答案，使用 bitset 存储哈希表避免超时。
5. 两种情况可以合并在一起处理，区别在于 $i$ 的枚举结束范围以及最终生成答案的过程。

时间复杂度

• 以每个位置开始求 KMP 的总时间复杂度为 $O(n^2)$。
• 第一种情况和第二种情况都需要在每个位置下，线性遍历枚举答案。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n + n^2/64)$ 的额外空间存储 $next$ 数组和哈希表。

C++ 代码

const int N = 5000;

class Solution {
public:
    int beautifulSplits(vector<int>& nums) {
        const int n = nums.size();

        vector<int> nxt(n);
        bitset<N*N> seen;

        int ans = 0;

        for (int s = 0; s < n; s++) {
            nxt[s] = s - 1;

            for (int i = s + 1, j = s - 1; i < n; i++) {
                while (j >= s && nums[i] != nums[j + 1])
                    j = nxt[j];

                if (nums[i] == nums[j + 1])
                    ++j;

                nxt[i] = j;
            }

            for (int i = s + 1; i < (s == 0 ? n - 1 : n); i += 2) {
                int j = nxt[i];

                if (j < s + (i - s - 1) / 2)
                    continue;

                if ((i - s + 1) / 2 % (i - j) != 0)
                    continue;

                if (s == 0) {
                    for (int k = i + 1; k < n; k++) {
                        seen.set((i + 1) / 2 * n + k);
                        ++ans;
                    }
                } else {
                    if (!seen.test(s * n + s + (i - s + 1) / 2)) {
                        seen.set(s * n + s + (i - s + 1) / 2);
                        ++ans;
                    }
                }
            }
        }

        return ans;
    }
};

算法2

(枚举，动态规划) $O(n^2)$

1. 设状态 $f(i, j)$ 表示分别以 $i$ 和 $j$ 为起始位置时，子数组的最大公共前缀。
2. 初始时，$f(i, j) = 0$。
3. 倒序转移，对于 $i$ 和 $j$，如果 $nums(i) = nums(j)$，则 $f(i, j) = f(i + 1, j + 1) + 1$，否则 $f(i, j) = 0$。
4. 枚举分割点 $i$ 和 $j$，即三个子数组分别为 $[0, i)$，$[i, j)$ 以及 $[j, n)$。
5. 如果 $nums1$ 的长度小于等于 $nums2$ 的长度，且 $f(0, i)$ 大于等于 $nums1$ 的长度，则答案加一。
6. 或者，如果 $nums2$ 的长度小于等于 $nums3$ 的长度，且 $f(i, j)$ 大于等于 $nums2$ 的长度，则答案也可以加一。

时间复杂度

• 动态规划的状态数为 $O(n^2)$，转移时间为常数。
• 枚举答案判定的时间复杂度为 $O(n^2)$。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要 $O(n^2)$ 的额外空间存储状态。

C++ 代码

const int N = 5010;

int f[N][N];

class Solution {
public:
    int beautifulSplits(vector<int>& nums) {
        const int n = nums.size();

        for (int i = n - 1; i >= 0; i--)
            for (int j = n - 1; j >= i; j--)
                f[i][j] = (nums[i] == nums[j]) ? f[i + 1][j + 1] + 1 : 0;

        int ans = 0;
        for (int i = 1; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                if ((i <= j - i && f[0][i] >= i) ||
                (j - i <= n - j && f[i][j] >= j - i))
                    ++ans;

        return ans;
    }
};