Python程序：查找列表中三个唯一元素，使其和最接近k

假设我们有一个名为 nums 的数字列表和另一个值 k，我们需要在 nums 中找到三个唯一的条目 (a、b、c)，使得 |a + b + c − k| 最小化，并返回绝对差值。

因此，如果输入类似于 nums = [2, 5, 25, 6] k = 14，则输出将为 1，因为如果我们取 [2, 5, 6] 将使我们最接近 14，并且绝对差值为 |13 − 14| = 1。

为了解决这个问题，我们将遵循以下步骤 -

  • 对列表 nums 进行排序

  • ans := 1^9

  • 对于范围从 0 到 nums 大小的 i，执行以下操作

    • j := i + 1

    • k := nums 大小 − 1

    • 当 j < k 时，执行以下操作

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

      • 如果 s <= target，则

        • ans := ans 和 target − s 的最小值

        • j := j + 1

      • 否则，

        • ans := ans 和 s − target 的最小值

        • k := k − 1

  • 返回 ans

让我们看看下面的实现以获得更好的理解 -

示例

 实时演示

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

输入

[2, 5, 25, 6], 14

输出

1

更新于: 2020年10月21日

191 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告