程序检查数组中三元组的数量，其和是否小于目标 Python

pythonserver side programmingprogramming更新于 2026/2/4 5:32:17

假设我们有一个名为 nums 的数字列表和另一个值目标，我们必须找到存在的三元组的数量 (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 的大小
对于范围为 0 到 n−1 的 i，执行
- 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))