程序查找唯一四个索引的数量,它们可以从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:=一个新列表
对于0到A的范围内的i,执行
在temp_list的末尾插入(A[i]+B[j])
对于范围0到B大小的j,执行
排序列表temp_list
回答:=0
对于0到C大小的i,执行
sum_cd:=C[i]+D[j]
sum_ab:=目标-sum_cd
ans:=ans+temp_list中其和<=sum_ab的元素数
对于范围0到D大小的j,执行
返回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