โปรแกรมหาสองคู่ตัวเลขที่ความต่างผลรวมน้อยที่สุดใน Python

สมมติว่ามีรายการตัวเลข nums ต้องการเลือกสองคู่ตัวเลข ที่ความต่างสัมบูรณ์ของผลรวมสองค้ือนั้นน้อยที่สุด

ตัวอย่าง: nums = [3, 4, 5, 10, 7] ผลลัพธ์คือ 1 เลือกคู่ (3+7) และ (4+5) ความต่าง = 1

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

1. สร้างรายการ distances เก็บ (|nums[i]-nums[j]|, i, j) สำหรับทุกคู่ i < j
2. เรียง distances
3. ans = 1e9
4. วนลูป i จาก 0 ถึง len(distances)-2:
   • ดึง dist, i1, i2 และ dist2, i3, i4 จาก j = i+1
   • ขยับ j จนกว่า index ทั้ง 4 จะไม่ซ้ำกัน
   • ถ้า index ไม่ซ้ำ: ans = min(ans, dist2 - dist)
5. คืนค่า ans

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

class Solution:
    def solve(self, nums):
        distances = []
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                distances.append((abs(nums[i] - nums[j]), i, j))
        distances.sort()
        ans = 1e9
        for i in range(len(distances) - 1):
            dist, i1, i2 = distances[i]
            j = i + 1
            dist2, i3, i4 = distances[j]
            while j < len(distances) and len({i1, i2, i3, i4}) != 4:
                dist2, i3, i4 = distances[j]
                j += 1
            if len({i1, i2, i3, i4}) == 4:
                ans = min(ans, dist2 - dist)
        return ans

ob = Solution()
nums = [3, 4, 5, 10, 7]
print(ob.solve(nums))

อินพุต

[3, 4, 5, 10, 7]

เอาต์พุต

1