Giả sử chúng ta có một danh sách các số gọi là num, chúng ta phải tìm số các dãy con có độ dài ≥ 3. Như chúng ta đã biết, một dãy số học là một danh sách các số mà hiệu số giữa một số và số tiếp theo là như nhau.
Vì vậy, nếu đầu vào là nums =[6, 12, 13, 8, 10, 14], thì đầu ra sẽ là 3, vì chúng ta có các dãy con như:[6, 8, 10], [6, 10, 14 ], [12, 13, 14].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
-
dp:=một bản đồ mới
-
n:=kích thước của nums
-
res:=0
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
đối với j trong phạm vi 0 đến i, thực hiện
-
diff:=nums [i] - nums [j]
-
trước:=dp [(i, diff)] nếu không có thì 0
-
presprev:=dp [(j, diff)] nếu không có thì là 0
-
dp [i, diff]:=prev + prevprev + 1
-
res:=res + presprev
-
-
-
trả lại res
Ví dụ
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)) Đầu vào
[6, 12, 13, 8, 10, 14]
Đầu ra
3