程序从总和小于或小于目标的数组中检查三元组的数量

假设我们有一个称为nums的数字列表和另一个值目标，我们必须找到存在的三元组（i <j <k）的数目，以使nums [i] + nums [j] + nums [k] <目标。

因此，如果输入像nums = [-2、6、4、3、8]，target = 12，则输出将是5，因为三元组是：[-2,6,4]，[-2 ，6,3]，[− 2,4,3]，[− 2,4,8]，[− 2,3,8]

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

• 排序列表编号

• 回答：= 0

• n：= nums的大小

• 对于范围在0到n-1之间的i

• 当k> j和nums [i] + nums [k] + nums [j]> =目标时，执行

• 如果j与k相同，则

• k：= k − 1

• k：= n − 1

• 对于范围为i +1到n-1的j

• 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