3299：连续子序列的和（★★）

Ian

2024-09-27 约 439 字预计阅读 1 分钟次阅读

力扣第 3299 题

题目

如果一个长度为 n 的数组 arr 符合下面其中一个条件，可以称它连续：

对于所有的 1 <= i < n，arr[i] - arr[i - 1] == 1。
对于所有的 1 <= i < n，arr[i] - arr[i - 1] == -1。

数组的值是其元素的和。

例如，[3, 4, 5] 是一个值为 12 的连续数组，并且 [9, 8] 是另一个值为 17 的连续数组。而 [3, 4, 3] 和 [8, 6] 都不连续。

给定一个整数数组 nums，返回所有连续非空子序列的值之和。

由于答案可能很大，返回它对 10⁹+ 7 取模的值。

注意长度为 1 的数组也被认为是连续的。

示例 1：

输入：nums = [1,2]

输出：6

解释：

连续子序列为 [1]，[2]，[1, 2]。

示例 2：

输入：nums = [1,4,2,3]

输出：31

解释：

连续子序列为：[1]，[4]，[2]，[3]，[1, 2]，[2, 3]，[4, 3]，[1, 2, 3]。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

分析

维护以 x 结尾的递增/减连续子序列个数和、子序列总和，即可递推
长度为 1 的子序列被统计了两次，减去即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def getSum(self, nums: List[int]) -> int:
        mod = 10**9+7
        def cal(A):
            f = defaultdict(int)
            g = defaultdict(int)
            for x in A:
                add = 1+f[x-1]
                f[x] = (f[x]+add)%mod
                g[x] = (g[x]+g[x-1]+x*add)%mod
            return sum(g.values())%mod   
        return (cal(nums)+cal(nums[::-1])-sum(nums))%mod  

769 ms

目录

3299：连续子序列的和（★★）

题目

分析

解答