Chương trình tìm ba phần tử duy nhất từ danh sách có tổng gần k nhất trong Python

Giả sử chúng ta có một danh sách các số gọi là nums và một giá trị k, chúng ta phải tìm ba mục duy nhất trong nums (a, b, c) sao cho |a + b + c - k| được tối thiểu hóa và trả về độ chênh lệch tuyệt đối.

Ví dụ, nếu đầu vào là nums = [2, 5, 25, 6], k = 14, thì đầu ra sẽ là 1 vì nếu lấy [2, 5, 6] sẽ gần 14 nhất và độ chênh lệch tuyệt đối là |13 - 14| = 1.

Để giải quyết, chúng ta thực hiện các bước sau:

• sắp xếp danh sách nums
• ans := 1e9 (vô cực)
• với i trong khoảng 0 đến kích thước nums:
  • j := i + 1
  • k := kích thước nums - 1
  • trong khi j < k:
    • s := nums[i] + nums[j] + nums[k]
    • nếu s <= target:
      • ans := min(ans, target - s)
      • j := j + 1
    • ngược lại:
      • ans := min(ans, s - target)
      • k := k - 1
• trả về ans

Ví dụ

class Solution:
    def solve(self, nums, target):
        nums.sort()
        ans = 1e9
        for i in range(len(nums)):
            j = i + 1
            k = len(nums) - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s <= target:
                    ans = min(ans, target - s)
                    j += 1
                else:
                    ans = min(ans, s - target)
                    k -= 1
        return ans

ob1 = Solution()
nums = [2, 5, 25, 6]
k = 14
print(ob1.solve(nums, k))

Input

[2, 5, 25, 6], 14

Output

1