Pythonの数のリストから算術サブシーケンスの数を見つけるプログラム？

numsと呼ばれる数のリストがあるとすると、長さが3以上の算術サブシーケンスの数を見つける必要があります。等差数列は、ある数と次の数の差が同じである数のリストです。

したがって、入力がnums =[6、12、13、8、10、14]のような場合、[6、8、10]、[6、10、14]のようなサブシーケンスがあるため、出力は3になります。 ]、[12、13、14]。

これを解決するには、次の手順に従います。

• dp：=新しいマップ

• n：=numsのサイズ

• res：=0

• 0からnの範囲のiの場合、実行

  • 0からiの範囲のjについては、次のようにします

    • diff：=nums [i]-nums [j]

    • prev：=dp [（i、diff）]それが存在しない場合は、0

    • prevprev：=dp [（j、diff）]それが存在しない場合は、0

    • dp [i、diff]：=prev + prevprev + 1

    • res：=res + prevprev

• 解像度を返す

例

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