Medium

题目描述

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一个 有效 划分：

  1. 子数组 恰好 由 2 个相等元素组成，例如，子数组 [2,2] 。
  2. 子数组 恰好 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
  3. 子数组 恰好 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。

如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

示例 1：

输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这个划分是有效的，所以返回 true 。

示例 2：

输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。

提示：

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

解题思路

解题思路

这是一道动态规划问题。我们需要判断数组是否可以被划分为符合条件的子数组。

核心思想： 设 dp[i] 表示前 i 个元素是否可以形成有效划分。对于位置 i，我们需要检查以第 i 个元素结尾的子数组是否满足三种条件之一：

  1. 长度为2的相等元素：nums[i-1] == nums[i]，且 dp[i-2] 为真
  2. 长度为3的相等元素：nums[i-2] == nums[i-1] == nums[i]，且 dp[i-3] 为真
  3. 长度为3的连续递增：nums[i-2] == nums[i-1]-1 == nums[i]-2，且 dp[i-3] 为真

状态转移：

  • 初始状态：dp[0] = true（空数组可以看作有效划分）
  • 转移方程：dp[i] = (条件1) || (条件2) || (条件3)

边界处理： 需要注意数组下标越界问题，在检查条件时要确保索引有效。

时间复杂度： O(n)，只需遍历一次数组 空间复杂度： O(n)，使用dp数组存储状态

这种方法通过动态规划自底向上地构建解，避免了重复计算，是最优解法。

代码实现

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        
        for (int i = 2; i <= n; i++) {
            // 检查长度为2的相等元素
            if (nums[i-1] == nums[i-2] && dp[i-2]) {
                dp[i] = true;
            }
            
            // 检查长度为3的相等元素
            if (i >= 3 && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && dp[i-3]) {
                dp[i] = true;
            }
            
            // 检查长度为3的连续递增
            if (i >= 3 && nums[i-1] == nums[i-2] + 1 && nums[i-2] == nums[i-3] + 1 && dp[i-3]) {
                dp[i] = true;
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * (n + 1)
        dp[0] = True
        
        for i in range(2, n + 1):
            # 检查长度为2的相等元素
            if nums[i-1] == nums[i-2] and dp[i-2]:
                dp[i] = True
            
            # 检查长度为3的相等元素
            if i >= 3 and nums[i-1] == nums[i-2] == nums[i-3] and dp[i-3]:
                dp[i] = True
            
            # 检查长度为3的连续递增
            if i >= 3 and nums[i-1] == nums[i-2] + 1 == nums[i-3] + 2 and dp[i-3]:
                dp[i] = True
        
        return dp[n]

public class Solution {
    public bool ValidPartition(int[] nums) {
        int n = nums.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
        
        for (int i = 2; i <= n; i++) {
            // 检查长度为2的相等元素
            if (nums[i-1] == nums[i-2] && dp[i-2]) {
                dp[i] = true;
            }
            
            // 检查长度为3的相等元素
            if (i >= 3 && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && dp[i-3]) {
                dp[i] = true;
            }
            
            // 检查长度为3的连续递增
            if (i >= 3 && nums[i-1] == nums[i-2] + 1 && nums[i-2] == nums[i-3] + 1 && dp[i-3]) {
                dp[i] = true;
            }
        }
        
        return dp[n];
    }
}

var validPartition = function(nums) {
    const n = nums.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    
    for (let i = 2; i <= n; i++) {
        // 检查长度为2的相等元素
        if (nums[i-1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，每个位置的状态转移为常数时间
空间复杂度O(n)使用dp数组存储每个位置的状态

相关题目