Python程序:检查数组中和小于目标值的三个数的个数


假设我们有一个名为nums的数字列表和另一个值target,我们需要找到存在多少个三元组 (i < j < k) 使得 nums[i] + nums[j] + nums[k] < target。

因此,如果输入类似于 nums = [−2, 6, 4, 3, 8],target = 12,则输出将为 5,因为三元组为:[−2,6,4],[−2,6,3],[−2,4,3],[−2,4,8],[−2,3,8]

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

  • 对列表nums进行排序

  • ans := 0

  • n := nums的长度

  • 对于i从0到n-1,执行:

    • k := n − 1

    • 对于j从i + 1到n-1,执行:

      • 当k > j 且 nums[i] + nums[k] + nums[j] >= target时,执行:

        • k := k − 1

      • 如果j等于k,则:

    • ans := ans + k − j

  • 返回ans

让我们来看下面的实现来更好地理解:

示例

在线演示

class Solution:
   def solve(self, nums, target):
      nums.sort()
      ans = 0
      n = len(nums)
      for i in range(n):
         k = n − 1
         for j in range(i + 1, n):
            while k > j and nums[i] + nums[k] + nums[j] >=
target:
               k -= 1
            if j == k:
               break
            ans += k − j
      return ans
ob1 = Solution()
nums = [−2, 6, 4, 3, 8]
target = 12
print(ob1.solve(nums, target))

输入

[-2, 6, 4, 3, 8], 12

输出

5

更新于:2020年10月21日

浏览量:153

开启您的职业生涯

完成课程获得认证

开始学习
广告