สมมุติว่าเรามีรายการของตัวเลขที่เรียกว่า 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 ทำ
-
สำหรับ j ในช่วง 0 ถึง i ทำ
-
diff :=nums[i] - nums[j]
-
ก่อนหน้า :=dp[(i, diff)] หากไม่มีอยู่ ให้ 0
-
prevprev :=dp[(j, diff)] หากไม่มีอยู่ แสดงว่าเป็น 0
-
dp[i, diff] :=ก่อนหน้า + ก่อนหน้า + 1
-
res :=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
