3351. Good Subsequences Sum

Sum of Good Subsequences

也是个难搞的题目呀 通过率36%一带 明显是难题中比较硬的那组

不过这种子序列计数求和题 还是能和我们给子数组计数异曲同工

正式讲第3351题之前 我先简单说下子数组和子序列的像与不像

子数组 子序列 同中存异 异中求同

A. 同：遍历到的元素尝试做『尾巴』

搜寻子数组时 我们让遍历到的索引$i$尝试做子数组尾

企图看有多少个结尾在索引$i$的子数组

那同理 亦能让遍历到的索引$i$做子序列尾呀

这样一来回圈逻辑清楚 再来也不会重复计算

B. 异：如何承上起下把家族传下去

双方最主要的分歧之一就在这儿 子数组讲究索引绝对的连续性

索引$i$只能帮所有结尾在索引$i - 1$的子数组延伸

但子序列允许索引之间跳著拿 爱拿谁就拿谁 相对顺序没变就好

换句话说 索引$i$能衔接所有结尾在索引$0, ..., i - 1$的子序列

现在有猜出3351道题咋整了齁

对于每个目前遍历到的索引$i$ 我们要看在前面$i$多次遍历中已经

出现过多少个 结尾值是$nums[i] - 1$或$nums[i] + 1$的子序列

因为题目有说 每个子序列 相邻元素 必须恰好有 1的绝对差

假设前面$i$多次遍历中有

I. $j$个结尾值是$nums[i] - 1$的子序列 所有子序列总和$Sum_{nums[i] - 1}$

II. $k$个结尾值是$nums[i] + 1$的子序列 所有子序列总和$Sum_{nums[i] + 1}$

那么我们立马判断出两个事实：

1. 结尾是 在索引$i$ 的子序列数量有$j + k + 1$个

2. 结尾值是$nums[i]$ 的子序列数量 净增加 $j + k + 1$个

注意1.和2.这两番话用语不太一样 因为 只有一个编号叫$i^{th}$的索引

但是在访问索引$i$之前 可能早有 结尾值是$nums[i]$的子序列成形

大家先细品 想清楚了这两句话 再往下阅读～～

--------------不要急😏慢慢来--------------

说回$j + k + 1$ 这$+ 1$是哪冒出来的呢？

别忘了 我们在索引$i$上 也有权选择抛弃继承

白手起家 让$nums[i]$自成一个子序列😛

计数搞定了 那求和就好办了 我们现在让：

(1). 结尾值$nums[i]$ 的子序列数量

净增加 $j + k + 1$个

(2). 结尾值$nums[i]$ 的子序列总和

净增加 $(Sum_{nums[i] - 1} + nums[i] * j) + (Sum_{nums[i] + 1} + nums[i] * k) + (nums[i])$

这边稍微复杂些 我放三对括号来逐一介绍在干嘛😄

a. 左首括号是索引$i$ 基于结尾值是$nums[i] - 1$的所有子序列做延伸

索引$i$继承结尾值是$nums[i] - 1$的所有子序列总和$Sum_{nums[i] - 1}$

$j$个结尾值$nums[i] - 1$子序列 都被$nums[i]$照顾

b. 中路括号是索引$i$ 基于结尾值是$nums[i] + 1$的所有子序列做延伸

索引$i$继承结尾值是$nums[i] + 1$的所有子序列总和$Sum_{nums[i] + 1}$

$k$个结尾值$nums[i] + 1$子序列 都被$nums[i]$照顾

c. 右首括号是索引$i$ 让$nums[i]$自成一个子序列

因此a.、b.、c.三部分加起来就是 结尾值$nums[i]$的子序列总和『淨增量』

等到遍历结束后我们就能把

不同子序列结尾值 它们各自子序列总和全部加起来

按规定除上$10^9 + 7$这个模控制大小就好了

但是大家应该察觉到了 子序列数量是O($2^n$)级别的

我们整个过程 一直使用子序列数量运算子序列总和

因此计算过程其实就要在子序列数量跟总和上

拿模来控制大小 避免数值爆炸溢位😉

☝️顺利控制到O(n)的时间和空间复杂度啰😺

C++

#include <vector>
#include <unordered_map>
using namespace std;

int sumGoodSubsequences(vector<int> &nums) // LeetCode Q.3351.
{
    long long modulo = pow(10, 9) + 7; // Long long prevents overflow.

    unordered_map<int, long long> subseqCounts, subseqSums;

    for (const auto &num : nums)
    {
        for (const auto &validTail : {num - 1, num + 1})
        {
            long long prevCount = subseqCounts[validTail];
            subseqCounts[num] += prevCount;

            long long prevSum = subseqSums[validTail];
            subseqSums[num] += prevSum + num * prevCount;
        }

        // Counts & sums are O(2^n) so must do modulo for future operations.
        subseqCounts[num] += 1;
        if (subseqCounts[num] > modulo)
            subseqCounts[num] %= modulo;

        subseqSums[num] += num;
        if (subseqSums[num] > modulo)
            subseqSums[num] %= modulo;
    }

    long long goodSubseqSum = 0;
    for (const auto &pair : subseqSums)
        goodSubseqSum += pair.second;

    return goodSubseqSum % modulo; // Control value size.
}

Python

def sum_good_subsequences(nums: list[int]) -> int:  # LeetCode Q.3351.
    modulo = 10 ** 9 + 7  # Prevents overflow.

    unique_nums = set(nums)

    subseqCounts: dict[int, int] = dict(
        zip(unique_nums, [0] * len(unique_nums))
    )

    subseqSums: dict[int, int] = dict(
        zip(unique_nums, [0] * len(unique_nums))
    )

    for num in nums:
        for validTail in (num - 1, num + 1):
            prev_count = subseqCounts.get(validTail, 0)
            subseqCounts[num] += prev_count

            prev_sum = subseqSums.get(validTail, 0)
            subseqSums[num] += prev_sum + num * prev_count

        # Counts & sums are O(2^n) so must do modulo for future operations.
        subseqCounts[num] += 1
        if subseqCounts[num] > modulo: subseqCounts[num] %= modulo

        subseqSums[num] += num
        if subseqSums[num] > modulo: subseqSums[num] %= modulo

    return sum(subseqSums.values()) % modulo  # Control value magnitude.

延伸问题

如果题目要求的不是子序列 而是子数组 最佳的时间和空间复杂度会有什么变化