Chương trình tìm hai cặp số có hiệu tổng nhỏ nhất trong Python

Mô tả bài toán

Cho danh sách nums. Chọn hai cặp số (4 chỉ số khác nhau) sao cho giá trị tuyệt đối của hiệu giữa tổng hai cặp là nhỏ nhất.

Ví dụ: nums = [3, 4, 5, 10, 7] → đầu ra 1 (cặp (3+7) và (4+5) cho hiệu 1).

Giải thuật

1. Tạo danh sách distances chứa tất cả các cặp (|nums[i]-nums[j]|, i, j) với i < j.
2. Sắp xếp distances theo giá trị chênh lệch.
3. Khởi tạo ans = 1e9.
4. Duyệt i từ 0 đến len(distances)-2:
   • Lấy dist, i1, i2 = distances[i].
   • Tìm j = i+1 sao cho 4 chỉ số i1,i2,i3,i4 đều khác nhau (lặp tăng j nếu trùng).
   • Nếu tìm thấy 4 chỉ số khác nhau: ans = min(ans, dist2 - dist).
5. Trả về ans.

Ví dụ mã Python

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))

Đầu vào

[3, 4, 5, 10, 7]

Đầu ra

1