มี 4 รายการ A,B,C,D และ target หาจำนวน quadruple (i,j,k,l) ที่ A[i]+B[j]+C[k]+D[l] ≤ target
เช่น A=[3,2] B=[5,3] C=[1] D=[2,3] target=9 ให้ 3
ขั้นตอนการแก้ปัญหา
- คำนวณผลรวมทุกคู่ A+B เก็บใน
temp_listแล้วเรียง - วนทุกคู่ C+D: หา
sum_ab = target - (C[i]+D[j]) - ใช้
bisect_rightหาจำนวนใน 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
