โปรแกรมค้นหาจำนวนดัชนีสี่ตัวที่ไม่ซ้ำกันซึ่งสามารถสร้างผลรวมน้อยกว่าเป้าหมายจากสี่รายการใน python

สมมติว่าเรามีรายการตัวเลข A, B, C และ D สี่รายการ และยังมีเป้าหมายตัวเลขอีกรายการหนึ่งด้วย เราต้องหาจำนวนของดัชนีเฉพาะที่แตกต่างกัน i, j, k, l ที่ A[i] + B[j] + C[k] + D[l] ≤ เป้าหมาย

ดังนั้นหากอินพุตเป็น A =[3, 2] B =[5, 3] C =[1] D =[2, 3] เป้าหมาย =9 ผลลัพธ์จะเป็น 3 ดังที่เราสามารถเลือกได้ดังต่อไปนี้ ชุดค่าผสม:[3, 3, 1, 2] [3, 3, 1, 2] [2, 3, 1, 3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• temp_list :=รายการใหม่
• สำหรับฉันในช่วง 0 ถึงขนาด A ทำ
  • สำหรับ j ในช่วง 0 ถึงขนาด B ให้ทำ
    • แทรก (A[i] + B[j]) ที่ส่วนท้ายของ temp_list
• เรียงลำดับรายการ temp_list
• ตอบ :=0
• สำหรับ i ในช่วง 0 ถึงขนาด C ให้ทำ
  • สำหรับ j ในช่วง 0 ถึงขนาด D ให้ทำ
    • sum_cd :=C[i] + D[j]
    • sum_ab :=เป้าหมาย - sum_cd
    • ans :=ans + จำนวนองค์ประกอบใน temp_list ซึ่งมีผลรวม <=sum_ab
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

3