โปรแกรมนับจำนวนลำดับเลขคณิตย่อยจากรายการตัวเลขใน Python

สมมติว่าเรามีรายการตัวเลข nums หาจำนวนลำดับเลขคณิต (arithmetic subsequences) ที่มีความยาว ≥ 3 ลำดับเลขคณิตคือลำดับที่ความต่างระหว่างตัวเลขติดกันคงที่ (ไม่จำเป็นต้องติดกันในอาร์เรย์เดิม)

ตัวอย่าง

อินพุต: nums = [6, 12, 13, 8, 10, 14]

เอาต์พุต: 3

ลำดับเลขคณิต: [6, 8, 10], [6, 10, 14], [12, 13, 14]

ขั้นตอนการแก้ปัญหา

ใช้ DP กับ dictionary เก็บจำนวนลำดับที่ลงท้ายที่ index i ด้วยความต่าง diff:

1. dp = {}, n = len(nums), res = 0
2. วน i จาก 0 ถึง n-1:
   • วน j จาก 0 ถึง i-1:
     • 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 (นับเฉพาะลำดับยาว ≥ 3)
3. คืนค่า res

การนำไปใช้ใน Python

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