0446：等差数列划分 II - 子序列（★★）

Ian

2016-03-21 约 563 字预计阅读 2 分钟次阅读

力扣第 446 题

题目

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
再例如，[1, 1, 2, 5, 7] 不是等差序列。

数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。

例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。

题目数据保证答案是一个 32-bit 整数。

示例 1：

输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：

输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。

提示：

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1

分析

#1

考虑求最后两个数是 x、y 的等差子序列个数（长度 2 也算）
- 显然只要知道以 x 结尾、等差为 y-x 的子序列个数
- 因此令 f[i][diff] 保存以 nums[i] 结尾、等差 diff 的子序列个数，即可递推
递推过程中，以 x 结尾、等差为 y-x 的子序列再加上 y，长度即 >=3，累加到结果中即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        res, n = 0, len(nums)
        f = [defaultdict(int) for _ in range(n)]
        for i in range(n):
            for j in range(i):
                diff = nums[i]-nums[j]
                f[i][diff] += 1+f[j][diff]
                res += f[j][diff]
        return res

653 ms

#2

还可以直接令 f[x][diff] 保存以 x 结尾、等差 diff 的子序列个数
注意 x 可能有多个，组成的长度 2 的 [x,y] 也有多个，因此要额外保存元素个数

解答

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


class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        d = defaultdict(lambda:defaultdict(int))
        ct = defaultdict(int)
        res = 0
        for y in nums:
            for x in list(ct):
                diff = y-x
                res += d[x][diff]
                d[y][diff] += d[x][diff]+ct[x]
            ct[y]+=1
        return res

826 ms

目录

0446：等差数列划分 II - 子序列（★★）

题目

分析

#1

#2

解答