Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

합계가 대상보다 작은 배열의 트리플렛 수를 확인하는 프로그램 Python

<시간/>

nums라는 숫자 목록과 다른 값 대상이 있다고 가정하고 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 :=숫자 크기

  • 범위 0에서 n−1에 있는 i에 대해 수행

    • k :=n − 1

    • i + 1 ~ n−1 범위의 j에 대해

      • k> j 및 nums[i] + nums[k] + nums[j]>=target, do

        • k :=k − 1

      • j가 k와 같으면

    • ans :=ans + k − j

  • 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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