Medium

题目描述

给你一个数组 nums。

如果一个数组 nums 的分割是美丽的，需要满足：

  • 数组 nums 被分为三个子数组：nums1、nums2 和 nums3，使得 nums 可以通过按顺序连接 nums1、nums2 和 nums3 形成。
  • 子数组 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]
输出：2
解释：
没有美丽分割。

提示：

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

解题思路

这道题的核心是找到满足条件的三个子数组分割方式。我们需要枚举所有可能的分割点，并检查是否满足前缀条件。

解题思路：

  1. 预处理前缀匹配长度：使用动态规划预计算任意两个位置开始的最长公共前缀长度。设 lcp[i][j] 表示从位置 i 和位置 j 开始的最长公共前缀长度。

  2. 枚举分割点：枚举第一个分割点 i（nums1 的结尾）和第二个分割点 j（nums2 的结尾），其中 1 <= i < j < n。

  3. 检查前缀条件：

    • 检查 nums1 是否为 nums2 的前缀：如果 lcp[0][i] >= i，说明 nums1 是 nums2 的前缀
    • 检查 nums2 是否为 nums3 的前缀：如果 lcp[i][j] >= n - j，说明 nums2 是 nums3 的前缀

  4. 统计结果：只要满足其中一个前缀条件，就计入答案。

时间复杂度优化：通过预处理 LCP 数组，避免了每次比较时的重复计算，将时间复杂度优化到 O(n²)。

这种方法充分利用了动态规划的思想，先预处理出有用的信息，再进行高效的枚举和判断。

代码实现

class Solution {
public:
    int beautifulSplits(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;
        
        // 预处理最长公共前缀
        vector<vector<int>> lcp(n + 1, vector<int>(n + 1, 0));
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (nums[i] == nums[j]) {
                    lcp[i][j] = lcp[i + 1][j + 1] + 1;
                }
            }
        }
        
        int count = 0;
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                // 检查 nums1 是否为 nums2 的前缀
                bool cond1 = lcp[0][i] >= i;
                // 检查 nums2 是否为 nums3 的前缀
                bool cond2 = lcp[i][j] >= (n - j);
                
                if (cond1 || cond2) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def beautifulSplits(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0
        
        # 预处理最长公共前缀
        lcp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if nums[i] == nums[j]:
                    lcp[i][j] = lcp[i + 1][j + 1] + 1
        
        count = 0
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                # 检查 nums1 是否为 nums2 的前缀
                cond1 = lcp[0][i] >= i
                # 检查 nums2 是否为 nums3 的前缀
                cond2 = lcp[i][j] >= (n - j)
                
                if cond1 or cond2:
                    count += 1
        
        return count

public class Solution {
    public int BeautifulSplits(int[] nums) {
        int n = nums.Length;
        if (n < 3) return 0;
        
        // 预处理最长公共前缀
        int[,] lcp = new int[n + 1, n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (nums[i] == nums[j]) {
                    lcp[i, j] = lcp[i + 1, j + 1] + 1;
                }
            }
        }
        
        int count = 0;
        for (int i = 1; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                // 检查 nums1 是否为 nums2 的前缀
                bool cond1 = lcp[0, i] >= i;
                // 检查 nums2 是否为 nums3 的前缀
                bool cond2 = lcp[i, j] >= (n - j);
                
                if (cond1 || cond2) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var beautifulSplits = function(nums) {
    const n = nums.length;
    let count = 0;
    
    // Try all possible split points
    for (let i = 1; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            const nums1 = nums.slice(0, i);
            const nums2 = nums.slice(i, j);
            const nums3 = nums.slice(j);
            
            // Check if nums1 is prefix of nums2
            const isPrefix1 = nums1.length <= nums2.length && 
                             nums1.every((val, idx) => val === nums2[idx]);
            
            // Check if nums2 is prefix of nums3
            const isPrefix2 = nums2.length <= nums3.length && 
                             nums2.every((val, idx) => val === nums3[idx]);
            
            if (isPrefix1 || isPrefix2) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)预处理 LCP 数组需要 O(n²)，枚举分割点需要 O(n²)
空间复杂度O(n²)LCP 数组需要 O(n²) 的空间