Hard

题目描述

给你一个整数数组 nums。好子序列定义为 nums 的一个子序列，其中子序列中任意两个连续元素的绝对差值恰好为 1。

返回 nums 所有可能的好子序列的和。

由于答案可能非常大，请返回对 10^9 + 7 取模的结果。

注意，长度为 1 的子序列按定义被认为是好的。

示例 1：

输入：nums = [1,2,1]
输出：14
解释：
好子序列有：[1], [2], [1], [1,2], [2,1], [1,2,1]。
这些子序列中元素的和为 14。

示例 2：

输入：nums = [3,4,5]
输出：40
解释：
好子序列有：[3], [4], [5], [3,4], [4,5], [3,4,5]。
这些子序列中元素的和为 40。

提示：

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

解题思路

这道题需要计算所有好子序列的和，其中好子序列要求相邻元素差值恰好为1。

核心思路是动态规划，我们需要维护两个状态：

  1. count[i]：以值 i 结尾的好子序列个数
  2. sum[i]：以值 i 结尾的所有好子序列的元素和

对于数组中的每个元素 x，它可以：

  • 单独形成一个子序列，贡献 1 个子序列，和为 x
  • 接在以 x-1 结尾的子序列后面，贡献 count[x-1] 个新子序列
  • 接在以 x+1 结尾的子序列后面，贡献 count[x+1] 个新子序列

状态转移方程：

  • 新的 count[x] = count[x-1] + count[x+1] + 1
  • 新的 sum[x] = sum[x-1] + sum[x+1] + x * (count[x-1] + count[x+1] + 1)

其中加1是因为 x 本身可以形成一个单元素子序列。

最后答案是所有 sum[i] 的总和。

代码实现

class Solution {
public:
    int sumOfGoodSubsequences(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        unordered_map<int, long long> count, sum;
        
        for (int x : nums) {
            long long prevCount = (count[x - 1] + count[x + 1]) % MOD;
            long long prevSum = (sum[x - 1] + sum[x + 1]) % MOD;
            
            count[x] = (prevCount + 1) % MOD;
            sum[x] = (prevSum + (long long)x * (prevCount + 1)) % MOD;
        }
        
        long long result = 0;
        for (auto& p : sum) {
            result = (result + p.second) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def sumOfGoodSubsequences(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        count = {}
        sum_val = {}
        
        for x in nums:
            prev_count = (count.get(x - 1, 0) + count.get(x + 1, 0)) % MOD
            prev_sum = (sum_val.get(x - 1, 0) + sum_val.get(x + 1, 0)) % MOD
            
            count[x] = (prev_count + 1) % MOD
            sum_val[x] = (prev_sum + x * (prev_count + 1)) % MOD
        
        return sum(sum_val.values()) % MOD

public class Solution {
    public int SumOfGoodSubsequences(int[] nums) {
        const int MOD = 1000000007;
        Dictionary<int, long> count = new Dictionary<int, long>();
        Dictionary<int, long> sum = new Dictionary<int, long>();
        
        foreach (int x in nums) {
            long prevCount = (count.GetValueOrDefault(x - 1, 0) + 
                            count.GetValueOrDefault(x + 1, 0)) % MOD;
            long prevSum = (sum.GetValueOrDefault(x - 1, 0) + 
                          sum.GetValueOrDefault(x + 1, 0)) % MOD;
            
            count[x] = (prevCount + 1) % MOD;
            sum[x] = (prevSum + (long)x * (prevCount + 1)) % MOD;
        }
        
        long result = 0;
        foreach (var kvp in sum) {
            result = (result + kvp.Value) % MOD;
        }
        
        return (int)result;
    }
}

var sumOfGoodSubsequences = function(nums) {
    const MOD = 1e9 + 7;
    const count = new Map();
    const sum = new Map();
    
    for (const x of nums) {
        const prevCount = ((count.get(x - 1) || 0) + (count.get(x + 1) || 0)) % MOD;
        const prevSum = ((sum.get(x - 1) || 0) + (sum.get(x + 1) || 0)) % MOD;
        
        count.set(x, (prevCount + 1) % MOD);
        sum.set(x, (prevSum + x * (prevCount + 1)) % MOD);
    }
    
    let result = 0;
    for (const val of sum.values()) {
        result = (result + val) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(k)

其中 n 是数组长度，k 是数组中不同元素的个数（最多为 min(n, 10^5)）。