Chương trình đếm số bộ ba từ mảng có tổng nhỏ hơn target trong Python

Giả sử chúng ta có một danh sách các số gọi là nums và một giá trị target, chúng ta phải tìm số lượng bộ ba (i < j < k) tồn tại sao cho nums[i] + nums[j] + nums[k] < target.

Ví dụ, nếu đầu vào là nums = [-2, 6, 4, 3, 8], target = 12, thì đầu ra sẽ là 5, vì các bộ ba là: [-2,6,4], [-2,6,3], [-2,4,3], [-2,4,8], [-2,3,8]

Để giải quyết, chúng ta thực hiện các bước sau:

• sắp xếp danh sách nums
• ans := 0
• n := kích thước nums
• với i trong khoảng 0 đến n-1:
  • k := n - 1
  • với j trong khoảng i + 1 đến n-1:
    • trong khi k > j VÀ nums[i] + nums[k] + nums[j] >= target:
      • k := k - 1
    • nếu j bằng k, thoát vòng lặp
    • ans := ans + k - j
• trả về ans

Ví dụ

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))

Input

[-2, 6, 4, 3, 8], 12

Output

5