Chương trình đếm số dãy con cấp số cộng liên tiếp độ dài ≥ 3 trong Python

Cho danh sách số nums. Đếm số dãy con liên tiếp (contiguous subarray) độ dài ≥ 3 là cấp số cộng.

Ví dụ

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

Các dãy cấp số cộng liên tiếp độ dài ≥ 3:

• [6, 8, 10] (diff=2)
• [8, 10, 12] (diff=2)
• [6, 8, 10, 12] (diff=2, độ dài 4)
• [12, 13, 14] (diff=1)

Kết quả: 4.

Thuật toán (Đếm độ dài dãy cấp số cộng liên tiếp)

1. Khởi tạo count = 0 (độ dài dãy cấp số cộng hiện tại - 2), ans = 0.
2. Duyệt i từ 2 đến n-1:
   • Nếu nums[i] - nums[i-1] == nums[i-1] - nums[i-2]: count++.
   • Ngược lại: ans += count * (count + 1) // 2, reset count = 0.
3. Sau vòng lặp: ans += count * (count + 1) // 2.
4. Trả về ans.

Công thức: dãy cấp số cộng độ dài L có (L-2)*(L-1)/2 dãy con độ dài ≥ 3.

Triển khai 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

# Test
ob = Solution()
print(ob.solve([6, 8, 10, 12, 13, 14]))  # Output: 4

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).

Bài toán "Arithmetic Slices" (LeetCode 413).