在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],target=9,则输出将是3,因为我们可以选择以下组合:[3,3,1,2] [3,3,1,2] [2,3,1,3]
为了解决这个问题,我们将按照以下步骤进行:
- temp_list := 新列表
- for i in range(0,size of A),do
- for j in range(0,size of B),do
- insert (A[i] + B[j]) at the end of temp_list
- for j in range(0,size of B),do
- 排序列表temp_list
- ans := 0
- for i in range(0,size of C),do
- for j in range(0,size of D),do
- sum_cd := C[i] + D[j]
- sum_ab := target – sum_cd
- ans := ans + temp_list中元素数,其总和<= sum_ab
- for j in range(0,size of D),do
- 返回ans
让我们看下面的实现以获得更好的理解:
示例
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