หาคู่ตัวเลขในเมทริกซ์ที่มีผลรวมกำหนดและอยู่คนละแถวใน Python

สมมติว่าเรามีเมทริกซ์ที่มีค่าไม่ซ้ำกัน และค่า Sum ต้องการหาคู่ตัวเลขที่มีผลรวมเท่ากับ Sum โดยตัวเลขแต่ละคู่ต้องมาจากแถวที่ต่างกัน

เช่น เมทริกซ์ 4x4, Sum = 13 ผลลัพธ์คือ [(2,11), (4,9), (3,10), (5,8), (12,1)]

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

1. เรียงลำดับแต่ละแถวในเมทริกซ์
2. สำหรับแต่ละคู่แถว (i, j) ใช้ Two Pointers หาคู่ที่ผลรวมเท่ากับ Sum

ตัวอย่างโค้ด Python

def sum_pair(matrix, target_sum):
    res = []
    n = len(matrix)
    for row in matrix:
        row.sort()
    for i in range(n - 1):
        for j in range(i + 1, n):
            low, high = 0, n - 1
            while low < n and high >= 0:
                s = matrix[i][low] + matrix[j][high]
                if s == target_sum:
                    res.append((matrix[i][low], matrix[j][high]))
                    low += 1
                    high -= 1
                elif s < target_sum:
                    low += 1
                else:
                    high -= 1
    return res

matrix = [
    [2, 4, 3, 5],
    [6, 9, 8, 7],
    [10, 11, 14, 12],
    [13, 1, 15, 16]
]
print(sum_pair(matrix, 13))

อินพุต

[[2,4,3,5], [6,9,8,7], [10,11,14,12], [13,1,15,16]], sum=13

เอาต์พุต

[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]