Chương trình tìm số lượng bốn chỉ số duy nhất nơi chúng có thể tạo tổng ít hơn mục tiêu từ bốn danh sách trong python

Giả sử chúng ta có bốn danh sách các số A, B, C và D và cũng có một mục tiêu số khác. Chúng ta phải tìm số lượng các chỉ số i, j, k, l khác nhau sao cho A [i] + B [j] + C [k] + D [l] ≤ target.

Vì vậy, nếu đầu vào là A =[3, 2] B =[5, 3] C =[1] D =[2, 3] target =9, thì đầu ra sẽ là 3, như chúng ta có thể chọn như sau kết hợp:[3, 3, 1, 2] [3, 3, 1, 2] [2, 3, 1, 3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• temp_list:=một danh sách mới
• đối với tôi trong phạm vi từ 0 đến kích thước là A, thực hiện
  • đối với j trong phạm vi từ 0 đến kích thước của B, thực hiện
    • chèn (A [i] + B [j]) vào cuối temp_list
• sắp xếp danh sách temp_list
• ans:=0
• đối với tôi trong phạm vi từ 0 đến kích thước là C, thực hiện
  • đối với j trong phạm vi từ 0 đến kích thước của D, thực hiện
    • sum_cd:=C [i] + D [j]
    • sum_ab:=target - sum_cd
    • ans:=ans + số phần tử trong temp_list có tổng <=sum_ab
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

from bisect import bisect_right

class Solution:
   def solve(self, A, B, C, D, target):
      temp_list = []
      for i in range(len(A)):
         for j in range(len(B)):
            temp_list.append(A[i] + B[j])

      temp_list.sort()

      ans = 0
      for i in range(len(C)):
         for j in range(len(D)):
            sum_cd = C[i] + D[j]
            sum_ab = target - sum_cd

            ans += bisect_right(temp_list, sum_ab)

      return ans

ob = Solution()
A = [3, 2]
B = [5, 3]
C = [1]
D = [2, 3]
target = 9
print(ob.solve(A, B, C, D, target))

Đầu vào

[3, 2], [5, 3], [1], [2, 3], 9

Đầu ra

3