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

สมมติว่าเรามีรายการตัวเลข nums หาจำนวนลำดับเลขคณิตที่ติดกัน (contiguous arithmetic sequences) ความยาว ≥ 3

ตัวอย่าง

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

เอาต์พุต: 4

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

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

วิธีง่าย: วนลูปตรวจสอบความต่างติดกัน:

1. count = 0, ans = 0
2. วน i จาก 2 ถึง len(nums)-1:
   • ถ้า nums[i] - nums[i-1] == nums[i-1] - nums[i-2]: count += 1
   • มิฉะนั้น: ans += count * (count + 1) // 2, count = 0
3. หลังลูป ถ้า count > 0: ans += count * (count + 1) // 2
4. คืนค่า ans

สูตร count*(count+1)/2 มาจากจำนวน subarrays ความยาว ≥ 3 ใน run ที่มีความต่างคงที่ยาว count+2

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

class Solution:
    def solve(self, nums):
        count = 0
        ans = 0
        for i in range(2, len(nums)):
            if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
                count += 1
            else:
                ans += (count * (count + 1)) // 2
                count = 0
        if count:
            ans += (count * (count + 1)) // 2
        return ans

ob = Solution()
nums = [6, 8, 10, 12, 13, 14]
print(ob.solve(nums))

อินพุต

[6, 8, 10, 12, 13, 14]

เอาต์พุต

4