โปรแกรมหาจำนวนการดำเนินการน้อยที่สุดลด X เป็นศูนย์ใน Python

ปัญหา

อาร์เรย์ nums และค่า x หนึ่งการดำเนินการ: ลบสมาชิกซ้ายสุดหรือขวาสุด แล้วลบค่าออกจาก x หาจำนวนการดำเนินการน้อยที่สุดทำให้ x=0 ถ้าไม่ได้คืน -1

ตัวอย่าง

nums=[4,2,9,1,4,2,3], x=9 → ผลลัพธ์ 3 (ลบซ้าย 4 → x=5, ลบขวา 3 → x=2, ลบซ้าย 2 หรือขวา 2 → x=0)

ขั้นตอนการแก้ปัญหา

1. n := len(nums)
2. leftMap := {0: -1}, left := 0
3. สร้าง prefix sum map: leftMap[left] = i (เก็บดัชนีแรกที่เจอ prefix sum นั้น)
4. right := 0, ans := n+1
5. วน i จาก n ถึง 0 (ย้อนกลับ):
   • ถ้า i < n: right += nums[i]
   • left := x - right
   • ถ้า left in leftMap: ans = min(ans, leftMap[left] + 1 + n - i)
6. ถ้า ans == n+1: คืน -1 มิฉะนั้น คืน ans

การนำไปใช้งาน (Python)

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 = x - right
        if left in leftMap:
            ans = min(ans, leftMap[left] + 1 + n - i)
    if ans == n + 1:
        return -1
    return ans

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

อินพุต

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

เอาต์พุต

3