Kiểm tra mảng có chứa các số liên tiếp (hỗ trợ số âm) trong Python O(n) time O(1) space

Cho mảng nums không sắp xếp, có thể chứa số âm. Kiểm tra xem các phần tử có tạo thành dãy số liên tiếp hay không.

Ví dụ: [-3, 5, 1, -2, -1, 0, 2, 4, 3] → các số từ -3 đến 5 liên tiếp → True.

Giải thuật

• Tìm giá trị nhỏ nhất init_term.
• Tính tổng của cấp số cộng từ init_term với công sai 1, độ dài n: ap_sum = n*(2*init_term + n-1)/2.
• Tính tổng thực tế của mảng. Nếu bằng ap_sum → True.

Mã ví dụ

def solve(nums):
    size = len(nums)
    init_term = 999999
    for i in range(size):
        if nums[i] < init_term:
            init_term = nums[i]
    ap_sum = (size * (2 * init_term + (size - 1) * 1)) // 2
    total = sum(nums)
    return ap_sum == total

nums = [-3, 5, 1, -2, -1, 0, 2, 4, 3]
print(solve(nums))

Đầu vào

[-3, 5, 1, -2, -1, 0, 2, 4, 3]

Đầu ra

True