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
广告