Chương trình tìm số phép toán tối thiểu giảm X về 0 trong Python

Cho mảng nums và giá trị x. Mỗi phép: xóa phần tử đầu hoặc cuối, trừ giá trị đó khỏi x. Tìm số phép nhỏ nhất để x về 0, -1 nếu không thể.

Ví dụ: nums=[4,2,9,1,4,2,3], x=9 → 3. Xóa 4 (trái), 3 (phải), 2 (trái/phải) → x=0.

Giải thuật (Prefix sum + Hash map)

1. Tính prefix sum từ trái, lưu map leftMap[sum] = index (chỉ lưu lần đầu xuất hiện).
2. Duyệt từ phải sang trái, tính suffix sum right.
3. Với mỗi right, cần left = x - right. Nếu left có trong leftMap: cập nhật ans = min(ans, leftMap[left] + 1 + n - i).
4. Trả về ans nếu tìm thấy else -1.

Ví dụ minh họa

def solve(nums, x):
    n = len(nums)
    leftMap = {0: -1}
    left = 0
    for i in range(n):
        left += nums[i]
        if left not in leftMap:
            leftMap[left] = i
    right = 0
    ans = n + 1
    for i in range(n, -1, -1):
        if i < n:
            right += nums[i]
        left_needed = x - right
        if left_needed in leftMap:
            ans = min(ans, leftMap[left_needed] + 1 + n - i)
    return ans if ans != n + 1 else -1

nums = [4,2,9,1,4,2,3]
x = 9
print(solve(nums, x))

Đầu vào

[4,2,9,1,4,2,3], 9

Đầu ra

3