K Prefix ใน Python

สมมติว่าเรามีรายการตัวเลข nums และจำนวนเต็ม k เราต้องหา i สูงสุดที่เป็นไปได้ โดยที่ nums[0] + nums[1] + ... + nums[i] ≤ k จะคืนค่า -1 หากไม่มี i ที่ถูกต้อง

ตัวอย่าง

หากอินพุตคือ nums = [4, -7, 5, 2, 6], k = 5 ผลลัพธ์จะเป็น 3 ดัชนีคือ 3 เนื่องจากถ้าบวก 4 + (-7) + 5 + 2 = 4 น้อยกว่า k ถ้าบวกตัวสุดท้ายจะไม่ต่ำกว่า k อีกต่อไป ดังนั้นดัชนีคือ 3

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

1. ลูป i จาก 1 ถึงขนาดของ nums - 1:
   • nums[i] := nums[i] + nums[i-1]
2. ลูป i จากขนาดของ nums - 1 ถึง -1 ลดทีละ 1:
   • ถ้า nums[i] <= k ให้คืนค่า i
3. คืนค่า -1

การใช้งาน

class Solution:
    def solve(self, nums, k):
        for i in range(1, len(nums)):
            nums[i] += nums[i-1]
        for i in range(len(nums)-1, -1, -1):
            if nums[i] <= k:
                return i
        return -1

ob = Solution()
nums = [4, -7, 5, 2, 6]
k = 5
print(ob.solve(nums, k))

อินพุต

[4, -7, 5, 2, 6], 5

เอาต์พุต

3