Python의 숫자 목록에서 산술 하위 시퀀스의 수를 찾는 프로그램은 무엇입니까?

<시간/>

nums라고 하는 숫자 목록이 있다고 가정하고 길이가 ≥ 3인 산술 하위 시퀀스의 수를 찾아야 합니다. 우리가 알고 있듯이 산술 시퀀스는 한 숫자와 다음 숫자의 차이가 동일한 숫자 목록입니다.

따라서 입력이 nums =[6, 12, 13, 8, 10, 14]와 같으면 출력은 [6, 8, 10], [6, 10, 14]와 같은 하위 시퀀스가 있으므로 3이 됩니다. ], [12, 13, 14].

이 문제를 해결하기 위해 다음 단계를 따릅니다.

dp :=새 지도
n :=숫자 크기
해상도 :=0
0에서 n 사이의 i에 대해 수행
- 범위 0에서 i까지의 j에 대해 수행
  - diff :=숫자[i] - 숫자[j]
  - prev :=dp[(i, diff)] 존재하지 않으면 0
  - prevprev :=dp[(j, diff)] 존재하지 않으면 0
  - dp[i, diff] :=이전 + 이전 이전 + 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]