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

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

Vì vậy, nếu đầu vào là nums =[2, 5, 25, 6] k =14, thì đầu ra sẽ là 1 vì nếu chúng ta lấy [2, 5, 6] sẽ cho chúng ta gần nhất với 14 và sự khác biệt tuyệt đối là | 13 - 14 | =1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp số lượng danh sách

• ans:=1 ^ 9

• đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện

  • j:=i + 1

  • k:=kích thước của nums - 1

  • trong khi j

    • s:=nums [i] + nums [j] + nums [k]

    • nếu s <=target thì

      • ans:=tối thiểu ans và target - s

      • j:=j + 1

    • nếu không,

      • ans:=tối thiểu ans và s - target

      • k:=k - 1

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

[2, 5, 25, 6], 14

Đầu ra

1