首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2025-06-04:好子序列的元素之和。用go语言,给定一个整数数组 nums,一个“好子序列”是指该子序列内任意相邻的两个元

2025-06-04:好子序列的元素之和。用go语言,给定一个整数数组 nums,一个“好子序列”是指该子序列内任意相邻的两个元

作者头像
福大大架构师每日一题
发布于 2025-06-06 07:19:49
发布于 2025-06-06 07:19:49
3300
代码可运行
举报
运行总次数:0
代码可运行

2025-06-04:好子序列的元素之和。用go语言,给定一个整数数组 nums,一个“好子序列”是指该子序列内任意相邻的两个元素之间的绝对差为1。

子序列是由原数组中删除若干元素(也可以不删除)后,保持元素相对顺序不变得到的新序列。

任务是计算 nums 中所有可能的好子序列的元素之和。由于结果可能很大,需要将最后结果对 1000000007 取模。

注:长度为1的子序列视为好子序列。

1 <= nums.length <= 100000。

0 <= nums[i] <= 100000。

输入:nums = [3,4,5]。

输出:40。

解释:

好子序列包括:[3], [4], [5], [3,4], [4,5], [3,4,5]。

这些子序列的元素之和为 40。

题目来自力扣3351。

问题描述

我们需要计算给定整数数组 nums 中所有“好子序列”的元素之和。好子序列的定义是子序列中任意相邻的两个元素的绝对差为1。子序列是通过删除原数组中的若干元素(可以不删除)而保持剩余元素的相对顺序得到的序列。长度为1的子序列也被视为好子序列。由于结果可能很大,需要对结果取模 1,000,000,007。

解题思路

我们需要高效地计算所有好子序列的元素之和。直接枚举所有可能的子序列并检查其是否为好子序列显然不可行,因为子序列的数量是指数级的。因此,我们需要一种动态规划的方法来高效地计算。

具体步骤

  1. 1. 初始化:
    • f 数组:大小为 max(nums) + 3,初始为0。
    • cnt 数组:大小为 max(nums) + 3,初始为0。
  2. 2. 遍历 nums 中的每个数字 x
    • • 计算新子序列的数量:c = cnt[x] + cnt[x+2] + 1
    • • 更新 f[x+1]f[x+1] = (f[x] + f[x+1] + f[x+2] + x * c) % mod
    • • 更新 cnt[x+1]cnt[x+1] = (cnt[x+1] + c) % mod
  3. 3. 计算所有 f 的和,并对 mod 取模。

时间复杂度和空间复杂度

  • • 时间复杂度:O(n + m),其中 nnums 的长度,mnums 中的最大值。我们需要遍历 nums 一次,并且每次更新操作是 O(1) 的。
  • • 空间复杂度:O(m),因为 fcnt 数组的大小与 nums 的最大值相关。在最坏情况下,m 可以是 100,000。

Go完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package main

import (
    "fmt"
    "slices"
)

func sumOfGoodSubsequences(nums []int) (ans int) {
    const mod = 1_000_000_007
    mx := slices.Max(nums)
    f := make([]int, mx+3)
    cnt := make([]int, mx+3)
    for _, x := range nums {
        // 为避免出现 -1,所有下标加一
        c := cnt[x] + cnt[x+2] + 1
        f[x+1] = (f[x] + f[x+1] + f[x+2] + x*c) % mod
        cnt[x+1] = (cnt[x+1] + c) % mod
    }

    for _, s := range f {
        ans += s
    }
    return ans % mod
}

func main() {
    nums := []int{3,4,5}
    result := sumOfGoodSubsequences(nums)
    fmt.Println(result)
}

Python完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# -*-coding:utf-8-*-

from typing importList

defsumOfGoodSubsequences(nums: List[int]) -> int:
    mod = 10**9 + 7
    mx = max(nums)
    f = [0] * (mx + 3)
    cnt = [0] * (mx + 3)
    for x in nums:
        c = (cnt[x] + cnt[x + 2] + 1) % mod  # 下标+1的等效处理
        f[x + 1] = (f[x] + f[x + 1] + f[x + 2] + x * c) % mod
        cnt[x + 1] = (cnt[x + 1] + c) % mod

    ans = sum(f) % mod
    return ans

if __name__ == "__main__":
    nums = [3, 4, 5]
    print(sumOfGoodSubsequences(nums))
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2025-06-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题描述
  • 解题思路
  • 具体步骤
  • 时间复杂度和空间复杂度
  • Go完整代码如下:
  • Python完整代码如下:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档