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

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

子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
子数组 恰 由 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
解释：该数组不存在有效划分。

动态规划

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1, 0);
        if(n == 2){
            return nums[1] == nums[0];
        }
        dp[0] = 1;
        dp[2] = nums[1] == nums[0];
        for(int i = 3; i < n+1; i++){
            if(nums[i-1] == nums[i-2]){
                dp[i] |= dp[i-2];
            }
            if(nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]){
                dp[i] |= dp[i-3];
            }
            if(nums[i-1] == nums[i-2]+1 && nums[i-2] == nums[i-3]+1){
                dp[i] |= dp[i-3];
            }
        }
        return dp[n];
    }
};

时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们仅遍历一次 nums。
时间复杂度：O(n)。数组 dp 消耗 O(n)。

我们定义一个dp，用来储存在前i个元素中，是否有至少一个有效划分。我们在遍历过程中，一旦发现此时最近的几个元素，能够满足三种有效划分情况的一种，我们根据在这几个元素之前是否也存在有效划分，如果存在，那么说明目前至少存在一种有效划分。

最后返回dp[n]即可。

空间优化

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        int n = nums.size();
        if (n == 2) {
            return nums[1] == nums[0];
        }

        // 只需要三个变量来存储之前的状态
        bool dp0 = true;              // 对应于 dp[i-3]
        bool dp1 = false;             // 对应于 dp[i-2]
        bool dp2 = nums[1] == nums[0]; // 对应于 dp[i-1]
        bool current = false;          // 用于存储 dp[i] 的值

        for (int i = 3; i <= n; i++) {
            current = false;
            if (nums[i - 1] == nums[i - 2]) {
                current |= dp1;
            }
            if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) {
                current |= dp0;
            }
            if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1) {
                current |= dp0;
            }
            
            // 更新 dp0, dp1, dp2
            dp0 = dp1;
            dp1 = dp2;
            dp2 = current;
        }

        return current;
    }
};

空间压缩至O(1)

通过对未压缩代码观察，我们发现我们在动态规划状态转移过程中，最多只用到当前元素和前面两个元素，那么说明我们可以用三个变量来储存这些状态，然后在遍历nums的过程中不断覆盖滚动。