用 Python 编写程序从数字列表中查找算术子序列的数量?

pythonserver side programmingprogramming更新于 2026/2/15 23:40:17

假设我们有一个名为 nums 的数字列表，我们必须找到长度 ≥ 的算术子序列的数量3. 我们知道，等差数列是一串数字，其中一个数字与下一个数字之间的差是相同的。

因此，如果输入为 nums = [6, 12, 13, 8, 10, 14]，则输出为 3，因为我们有子序列，如:[6, 8, 10], [6, 10, 14], [12, 13, 14]。

为了解决这个问题，我们将遵循以下步骤:

dp := a new map
n := size of nums
res := 0
for i in range 0 to n, do
- for j in range 0 到 i，执行
  - diff := nums[i] - nums[j]
  - prev := dp[(i, diff)] 如果不存在，则为 0
  - prevprev := 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))