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

Arnab Chakraborty

更新於：2020年10月21日

瀏覽量：153

開啟您的職業生涯

完成課程獲得認證

開始學習