โปรแกรมหาขนาดสับลิสต์น้อยที่สุดที่ผลรวม ≥ target ใน Python

คำอธิบายโจทย์

ให้ nums และ target หาความยาว subarray สั้นที่สุดที่ sum ≥ target ไม่มีคืน -1

ตัวอย่าง

nums = [2, 11, -4, 17, 4], target = 19 → 2 (subarray [17, 4])

วิธีแก้ปัญหา

Prefix Sum + Monotonic Queue (Sliding Window Minimum):

1. สร้าง prefix sum array ps
2. Monotonic queue q เก็บ index ของ ps ที่เพิ่มขึ้น (เพื่อหา ps[i] - ps[j] ≥ target)
3. สำหรับแต่ละ i: ขยาย j ใน q ขณะ ps[i] - ps[q[j]] ≥ target อัปเดต min_size
4. รักษา q ให้ monotonic increasing โดย pop ท้ายเมื่อ ps[i] ≤ ps[q[-1]]

โค้ด Python

class Solution:
    def solve(self, nums, target):
        ps = [0]
        for num in nums:
            ps += [ps[-1] + num]
            if num >= target:
                return 1
        
        min_size = float("inf")
        q = [0]
        j = 0
        for i in range(1, len(ps)):
            j = min(j, len(q) - 1)
            while j < len(q) and ps[i] - ps[q[j]] >= target:
                min_size = min(min_size, i - q[j])
                j += 1
            while q and ps[i] <= ps[q[-1]]:
                q.pop()
            q.append(i)
        
        return min_size if min_size < float("inf") else -1

ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))

อินพุต

[2, 11, -4, 17, 4], 19

เอาต์พุต

2