Chương trình kiểm tra mảng con có thể sắp thành cấp số cộng trong Python

Cho mảng nums và m truy vấn [l[i], r[i]]. Với mỗi truy vấn, kiểm tra mảng con nums[l[i]..r[i]] có thể sắp xếp thành cấp số cộng (chênh lệch giữa các phần tử liên tiếp bằng nhau) không.

Ví dụ: nums=[6,8,7,11,5,9], l=[0,0,2], r=[2,3,5] → [True, False, True]. [6,8,7]→[6,7,8] OK; [6,8,7,11] không OK; [7,11,5,9]→[5,7,9,11] OK.

Giải thuật

1. Khởi tạo kết quả new toàn True.
2. Với mỗi truy vấn i:
   • Lấy mảng con, sắp xếp.
   • Tính các chênh lệch liên tiếp, đưa vào set.
   • Nếu set có > 1 phần tử → không phải cấp số cộng → new[i] = False.

Ví dụ minh họa

def solve(nums, l, r):
    new = [True] * len(l)
    for i in range(len(l)):
        data = nums[l[i]:r[i]+1]
        data.sort()
        d = set()
        for j in range(len(data) - 1):
            d.add(data[j+1] - data[j])
        if len(d) != 1:
            new[i] = False
    return new

nums = [6,8,7,11,5,9]
l = [0,0,2]
r = [2,3,5]
print(solve(nums, l, r))

Đầu vào

[6,8,7,11,5,9], [0,0,2], [2,3,5]

Đầu ra

[True, False, True]