Chương trình đếm truy vấn tìm dãy số học trong mảng Python

Cho mảng nums và danh sách truy vấn queries (mỗi truy vấn [i,j]). Kiểm tra dãy con nums[i:j+1] có phải dãy số học không. Đếm số truy vấn trả về True.

Ví dụ: nums=[2,4,6,8,7,6,5,2], queries=[[3,4],[0,3],[2,4]] → 2 (dãy [2,4,6,8] và [8,7] là số học).

Giải thuật (Run-length encoding độ chênh lệch)

1. Tính mảng diff[i] = nums[i+1] - nums[i]
2. Tính rle[i] = độ dài dãy con kết thúc tại i có diff giống nhau
3. Truy vấn [i,j] là số học nếu rle[j-1] >= j-i (hoặc i==j)

Ví dụ triển khai

def solve(nums, queries):
    if not nums:
        return 0
    n = len(nums)
    diff = [nums[i+1] - nums[i] for i in range(n-1)]
    rle = [0] * (n-1)
    for i in range(n-1):
        if i > 0 and diff[i] == diff[i-1]:
            rle[i] = rle[i-1] + 1
        else:
            rle[i] = 1
    ans = 0
    for i, j in queries:
        if i == j:
            ans += 1
        else:
            ans += rle[j-1] >= (j - i)
    return ans

print(solve([2,4,6,8,7,6,5,2], [[3,4],[0,3],[2,4]]))

Đầu vào

[2,4,6,8,7,6,5,2], [[3,4],[0,3],[2,4]]

Đầu ra

2