合計がターゲットより少ないかPythonでない配列からトリプレットの数をチェックするプログラム

numsと呼ばれる数値のリストと別の値のターゲットがあるとすると、nums [i] + nums [j] + nums [k]

したがって、入力がnums =[-2、6、4、3、8]、target =12の場合、トリプレットは[-2,6,4]、[-2）であるため、出力は5になります。 、6,3]、[-2,4,3]、[-2,4,8]、[-2,3,8]

これを解決するには、次の手順に従います-

• リスト番号を並べ替える

• ans：=0

• n：=numsのサイズ

• 0からn-1の範囲のiの場合、実行

  • k：=n − 1

  • i + 1からn-1の範囲のjについては、次のようにします

    • k>jおよびnums[i]+ nums [k] + nums [j]> =ターゲットの場合、実行

      • 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