โปรแกรมหาผลรวมสองจำนวนที่น้อยกว่าเป้าหมายใน Python

สมมติว่าเรามีรายการตัวเลขชื่อ nums และค่าเป้าหมาย target เราต้องหาผลรวมของคู่ตัวเลขที่ใหญ่ที่สุดใน nums ที่ผลรวมไม่เกิน target - 1

เช่น ถ้าอินพุตคือ nums = [8, 3, 4, 9, 2], target = 8 ผลลัพธ์จะเป็น 7 เพราะคู่ที่ใหญ่ที่สุดน้อยกว่า 8 คือ 4 + 3 = 7

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

1. เรียงลำดับ nums
2. p1 := 0, p2 := ขนาดของ nums - 1, m := -inf
3. ในขณะที่ p1 < p2:
   • ถ้า nums[p1] + nums[p2] < target:
     • m := max(m, nums[p1] + nums[p2])
     • p1 := p1 + 1
   • มิฉะนั้น p2 := p2 - 1
4. คืนค่า m

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

import math

def solve(nums, target):
    nums.sort()
    p1 = 0
    p2 = len(nums) - 1
    m = -math.inf
    while p1 < p2:
        if nums[p1] + nums[p2] < target:
            m = max(m, nums[p1] + nums[p2])
            p1 += 1
        else:
            p2 -= 1
    return m

nums = [8, 3, 4, 9, 2]
target = 8
print(solve(nums, target))

อินพุต

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

เอาต์พุต

7