LeetCode 题解工作台
统计数组中的美丽分割
给你一个整数数组 nums 。 如果数组 nums 的一个分割满足以下条件，我们称它是一个 美丽 分割： 数组 nums 分为三段 非空子数组 ： nums1 ， nums2 和 nums3 ，三个数组 nums1 ， nums2 和 nums3 按顺序连接可以得到 nums 。 子数组 nums1…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以预处理 表示 和 的最长公共前缀长度。初始时 $\text{LCP}[i][j] = 0$。 接下来，我们倒序枚举 和 ，对于每一对 和 ，如果 $\textit{nums}[i] = \textit{nums}[j]$，那么我们可以得到 $\text{LCP}[i][j] = \text{LCP}[i + 1][j + 1] + 1$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 nums 。
如果数组 nums 的一个分割满足以下条件，我们称它是一个 美丽 分割：
- 数组
nums分为三段 非空子数组：nums1，nums2和nums3，三个数组nums1，nums2和nums3按顺序连接可以得到nums。 - 子数组
nums1是子数组nums2的 前缀 或者nums2是nums3的 前缀。
请你返回满足以上条件的分割 数目 。
子数组 指的是一个数组里一段连续 非空 的元素。
前缀 指的是一个数组从头开始到中间某个元素结束的子数组。
示例 1：
输入：nums = [1,1,2,1]
输出：2
解释：
美丽分割如下：
nums1 = [1]，nums2 = [1,2]，nums3 = [1]。nums1 = [1]，nums2 = [1]，nums3 = [2,1]。
示例 2：
输入：nums = [1,2,3,4]
输出：0
解释：
没有美丽分割。
提示：
1 <= nums.length <= 50000 <= nums[i] <= 50
解题思路
方法一：LCP + 枚举
我们可以预处理 表示 和 的最长公共前缀长度。初始时 。
接下来，我们倒序枚举 和 ，对于每一对 和 ，如果 ，那么我们可以得到 。
最后，我们枚举第一个子数组的结尾位置 （不包括位置 ），以及第二个子数组的结尾位置 （不包括位置 ），那么第一个子数组的长度为 ，第二个子数组的长度为 ，第三个子数组的长度为 。如果 且 ，或者 且 ，那么这个分割是美丽的，答案加一。
枚举结束后，答案即为美丽的分割数目。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def beautifulSplits(self, nums: List[int]) -> int:
n = len(nums)
lcp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(n - 1, i - 1, -1):
if nums[i] == nums[j]:
lcp[i][j] = lcp[i + 1][j + 1] + 1
ans = 0
for i in range(1, n - 1):
for j in range(i + 1, n):
a = i <= j - i and lcp[0][i] >= i
b = j - i <= n - j and lcp[i][j] >= j - i
ans += int(a or b)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the chosen implementation of prefix and suffix tracking. A direct frequency array approach gives O(n) per update with O(n) space, while more naive counting can reach O(n^2). Space complexity depends on storing frequency counts for each split, generally O(n) or O(maxValue). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Recognizes DP pattern with prefix and suffix frequency states.
- question_mark
Checks understanding of unique element counting and state transitions.
- question_mark
Tests ability to avoid recomputation and handle incremental updates efficiently.
常见陷阱
外企场景- error
Recomputing unique counts from scratch for each split instead of using incremental updates.
- error
Incorrectly updating frequency maps when elements move between left and right segments.
- error
Off-by-one errors in split point iteration leading to missed or extra counts.
进阶变体
外企场景- arrow_right_alt
Count beautiful splits when the split condition depends on sum equality instead of unique elements.
- arrow_right_alt
Find splits where one side contains a fixed set of elements and count valid partitions.
- arrow_right_alt
Modify the problem to allow k-way splits with similar uniqueness constraints.