資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告