Hard

题目描述

如果一个序列由若干个 0，然后是若干个 1，最后是若干个 2 组成，那么这个序列是特殊序列。

  • 例如，[0,1,2] 和 [0,0,1,1,1,2] 是特殊序列。
  • 相反，[2,1,0]、[1] 和 [0,1,2,0] 不是特殊序列。

给你一个只包含整数 0、1、2 的数组 nums，返回不同特殊子序列的数目。由于答案可能很大，请返回对 10^9 + 7 取余的结果。

数组的子序列是从数组中删除某些元素（可能不删除）后，不改变其余元素顺序得到的序列。如果两个子序列对应的下标集合不同，则认为这两个子序列不同。

示例 1：

输入：nums = [0,1,2,2]
输出：3
解释：特殊子序列为 [0,1,2,2]、[0,1,2,2] 和 [0,1,2,2]。

示例 2：

输入：nums = [2,2,0,0]
输出：0
解释：[2,2,0,0] 中没有特殊子序列。

示例 3：

输入：nums = [0,1,2,0,1,2]
输出：7
解释：特殊子序列有7个。

约束条件：

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

解题思路

解题思路

这是一道典型的动态规划问题。我们需要统计满足"先0后1再2"模式的子序列数量。

核心思路

我们可以维护三个状态变量：

  • dp0：以0结尾的有效子序列数量（只包含0的子序列）
  • dp1：以1结尾的有效子序列数量（包含0和1的子序列，符合0+1+模式）
  • dp2：以2结尾的有效子序列数量（包含0、1、2的完整特殊子序列）

状态转移

遍历数组中的每个元素：

  1. 遇到0时：

    • 可以开始一个新的子序列：dp0 += 1
    • 也可以延续之前以0结尾的子序列：dp0 += dp0
    • 即：dp0 = (dp0 * 2 + 1) % MOD

  2. 遇到1时：

    • 可以将任何以0结尾的子序列扩展为以1结尾：dp1 += dp0
    • 也可以延续之前以1结尾的子序列：dp1 += dp1
    • 即：dp1 = (dp1 * 2 + dp0) % MOD

  3. 遇到2时：

    • 可以将任何以1结尾的子序列扩展为完整的特殊子序列：dp2 += dp1
    • 也可以延续之前以2结尾的子序列：dp2 += dp2
    • 即：dp2 = (dp2 * 2 + dp1) % MOD

这种方法的精妙之处在于，每次遇到相同数字时，我们既可以选择加入已有的子序列，也可以选择不加入，从而正确地计算了所有可能的组合。

时间复杂度：O(n)，空间复杂度：O(1)。

代码实现

class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        long long dp0 = 0, dp1 = 0, dp2 = 0;
        
        for (int num : nums) {
            if (num == 0) {
                dp0 = (dp0 * 2 + 1) % MOD;
            } else if (num == 1) {
                dp1 = (dp1 * 2 + dp0) % MOD;
            } else { // num == 2
                dp2 = (dp2 * 2 + dp1) % MOD;
            }
        }
        
        return dp2;
    }
};

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        dp0 = dp1 = dp2 = 0
        
        for num in nums:
            if num == 0:
                dp0 = (dp0 * 2 + 1) % MOD
            elif num == 1:
                dp1 = (dp1 * 2 + dp0) % MOD
            else:  # num == 2
                dp2 = (dp2 * 2 + dp1) % MOD
        
        return dp2

public class Solution {
    public int CountSpecialSubsequences(int[] nums) {
        const int MOD = 1000000007;
        long dp0 = 0, dp1 = 0, dp2 = 0;
        
        foreach (int num in nums) {
            if (num == 0) {
                dp0 = (dp0 * 2 + 1) % MOD;
            } else if (num == 1) {
                dp1 = (dp1 * 2 + dp0) % MOD;
            } else { // num == 2
                dp2 = (dp2 * 2 + dp1) % MOD;
            }
        }
        
        return (int)dp2;
    }
}

var countSpecialSubsequences = function(nums) {
    const MOD = 1000000007;
    let zeros = 0, ones = 0, twos = 0;
    
    for (let num of nums) {
        if (num === 0) {
            zeros = (zeros * 2 + 1) % MOD;
        } else if (num === 1) {
            ones = (ones * 2 + zeros) % MOD;
        } else {
            twos = (twos * 2 + ones) % MOD;
        }
    }
    
    return twos;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需要遍历数组一次
空间复杂度O(1)只使用了常数个变量存储状态