2025-07-02：统计数组中的美丽分割。用go语言，给定一个整数数组 nums，
我们要把它划分成三个连续且非空的子数组 nums1、nums2、nums3，且这三个子数组按顺序拼接后还原为原数组 nums。

这样划分被称为“美丽分割”，条件是：

o 要么 nums1 是 nums2 的前缀（即 nums2 开头的一部分）

o 要么 nums2 是 nums3 的前缀（即 nums3 开头的一部分）

求满足以上条件的所有划分方案的数量。

1 <= nums.length <= 5000。

0 <= nums[i] <= 50。

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

输出：2。

解释：

美丽分割如下：

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

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

题目来自力扣3388 。

解决思路

为了高效地解决这个问题，我们可以利用 Z 算法（Z-array）来预处理字符串的前缀匹配信息。Z 数组可以帮助我们快速判断一个子数组是否是另一个子数组的前缀。

步骤 1：理解 Z 数组

Z 数组 z[i] 表示从位置 i 开始的子串与原字符串的前缀的最长公共长度。例如：

o 对于字符串 s，z[i] 是最大的 k 使得 s[0..k-1] == s[i..i+k-1]。

步骤 2：预处理 Z 数组

我们需要为原始数组 nums 和所有可能的 nums[i:] 子数组计算 Z 数组：

1. 计算 z0：z0 是 nums 的 Z 数组。z0[i] 表示 nums[i..] 与 nums 的前缀的最长公共长度。

2. 对于每个可能的 i（nums2 的起始位置），计算 z：z 是 nums[i..] 的 Z 数组。z[j] 表示 nums[i+j..] 与 nums[i..] 的前缀的最长公共长度。

步骤 3：枚举所有可能的划分

我们需要枚举所有可能的 i 和 j：

o i：nums2 的起始位置（nums1 是 nums[0..i-1]）。

o j：nums3 的起始位置（nums2 是 nums[i..j-1]，nums3 是 nums[j..n-1]）。

对于每个 (i, j) 对，检查以下条件之一是否成立：

1. nums1 是 nums2 的前缀：

o 即 nums[0..i-1] 是 nums[i..j-1] 的前缀。

o 等价于 z0[i] >= i（因为 nums[i..i+i-1] 应该等于 nums[0..i-1]）。

2. nums2 是 nums3 的前缀：

o 即 nums[i..j-1] 是 nums[j..n-1] 的前缀。

o 等价于 z[j-i] >= j-i（因为 nums[j..j+(j-i)-1] 应该等于 nums[i..j-1]）。

步骤 4：统计满足条件的划分

对于每个 i（从 1 到 n-2）和 j（从 i+1 到 n-1），检查上述条件。如果任一条件满足，则计数加一。

时间复杂度

1. 计算 z0：O(n)。

2. 对于每个 i（O(n)），计算 nums[i:] 的 Z 数组：O(n)。

o 总共有 O(n) 次 Z 数组计算，每次 O(n)，因此总时间为 O(n^2)。

3. 枚举所有 (i, j)：O(n^2)。

o 对于每个 i，j 从 i+1 到 n-1，共 O(n^2) 次检查。

o 每次检查是 O(1)（直接查 Z 数组）。

o 总时间复杂度：O(n^2)（预处理） + O(n^2)（枚举检查） = O(n^2)。

空间复杂度

1. 存储 z0：O(n)。

2. 对于每个 i，存储 nums[i:] 的 Z 数组：每次计算后可以复用或丢弃，因此只需要 O(n) 临时空间。

o 总空间复杂度：O(n)（用于存储 Z 数组）。

总结

o 总时间复杂度：O(n^2)。

o 总空间复杂度：O(n)。

Go完整代码如下：

package main

import (
    "fmt"
)

func calcZ(s []int) []int {
    n := len(s)
    z := make([]int, n)
    boxL, boxR := 0, 0// z-box 左右边界
    for i := 1; i < n; i++ {
        if i <= boxR {
            z[i] = min(z[i-boxL], boxR-i+1)
        }
        for i+z[i] < n && s[z[i]] == s[i+z[i]] {
            boxL, boxR = i, i+z[i]
            z[i]++
        }
    }
    return z
}

func beautifulSplits(nums []int) (ans int) {
    n := len(nums)
    z0 := calcZ(nums)
    for i := 1; i < n-1; i++ {
        z := calcZ(nums[i:])
        for j := i + 1; j < n; j++ {
            if i <= j-i && z0[i] >= i || z[j-i] >= j-i {
                ans++
            }
        }
    }
    return
}

func main() {
    nums := []int{1, 1, 2, 1}
    result := beautifulSplits(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def calcZ(s):
    n = len(s)
    z = [0] * n
    boxL, boxR = 0, 0  # Z-box 左右边界
    for i in range(1, n):
        if i <= boxR:
            z[i] = min(z[i - boxL], boxR - i + 1)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            boxL, boxR = i, i + z[i]
            z[i] += 1
    return z

def beautifulSplits(nums):
    n = len(nums)
    ans = 0
    z0 = calcZ(nums)
    for i in range(1, n - 1):
        z = calcZ(nums[i:])
        for j in range(i + 1, n):
            if (i <= j - i and z0[i] >= i) or (z[j - i] >= j - i):
                ans += 1
    return ans

if __name__ == "__main__":
    nums = [1, 1, 2, 1]
    result = beautifulSplits(nums)
    print(result)

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·