数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python程序：查找数字列表中算术子序列的数量？
假设我们有一个名为nums的数字列表，我们需要找到长度≥3的算术子序列的数量。众所周知，算术序列是一个数字列表，其中一个数字与下一个数字之间的差是相同的。
因此，如果输入类似于nums = [6, 12, 13, 8, 10, 14]，则输出将为3，因为我们有如下子序列：[6, 8, 10]，[6, 10, 14]，[12, 13, 14]。
为了解决这个问题，我们将遵循以下步骤：
dp := 一个新的映射
n := nums的大小
res := 0
对于范围从0到n的i，执行：
对于范围从0到i的j，执行：
diff := nums[i] - nums[j]
prev := 如果存在dp[(i, diff)]，则为dp[(i, diff)]，否则为0
prevprev := 如果存在dp[(j, diff)]，则为dp[(j, diff)]，否则为0
dp[i, diff] := prev + prevprev + 1
res := res + prevprev
返回res
示例
class Solution:
def solve(self, nums):
dp = {}
n = len(nums)
res = 0
for i in range(n):
for j in range(i):
diff = nums[i] - nums[j]
prev = dp.get((i, diff), 0)
prevprev = dp.get((j, diff), 0)
dp[(i, diff)] = prev + prevprev + 1
res += prevprev
return res
ob = Solution()
nums = [6, 12, 13, 8, 10, 14]
print(ob.solve(nums))输入
[6, 12, 13, 8, 10, 14]
输出
3
更新于：2020年11月10日
350 次浏览
广告