โปรแกรมตรวจสอบว่าผลรวมสองจำนวนเท่ากับ k จากรายการเรียงลำดับหรือไม่ใน Python

สมมติว่าเรามีรายการตัวเลขชื่อ nums เรียงลำดับจากน้อยไปมาก เรายังมีค่า k ต้องตรวจสอบว่ามีสองสมาชิกในรายการที่บวกกันได้ k หรือไม่ ตัวเลขอาจเป็นลบหรือศูนย์ ต้องแก้ปัญหาแบบใช้พื้นที่คงที่ (constant space)

เช่น ถ้าอินพุตคือ nums = [-8, -3, 2, 7, 9], k = 4 ผลลัพธ์จะเป็น True เพราะ 7 + (-3) = 4 เท่ากับ k

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

1. i := 0, j := ขนาดของ nums - 1
2. ในขณะที่ i < j:
   • cur_sum := nums[i] + nums[j]
   • ถ้า cur_sum == k คืนค่า True
   • มิฉะนั้นถ้า cur_sum < k ให้ i := i + 1
   • มิฉะนั้น j := j - 1
3. คืนค่า False

ตัวอย่างการใช้งาน

def solve(nums, k):
    i = 0
    j = len(nums) - 1
    while i < j:
        cur_sum = nums[i] + nums[j]
        if cur_sum == k:
            return True
        elif cur_sum < k:
            i += 1
        else:
            j -= 1
    return False

nums = [-8, -3, 2, 7, 9]
k = 4
print(solve(nums, k))

อินพุต

[-8, -3, 2, 7, 9], 4

เอาต์พุต

True