从给定的两个数组中查找子数组，以便它们在Python中的总和相等
假设我们有两个数组P和Q，它们的大小为N，它们的个数为1到N。我们必须从给定数组中找到子数组，以使它们具有相等的总和。最后返回这些子数组的索引。如果没有解决方案，则返回-1。
因此，如果输入像P = [2、3、4、5、6]，Q = [9、3、2、6、5]，则输出将是第一个数组中的索引：0、1、2以及第二个数组中的索引：0，所以P [0..2] = 2 + 3 + 4 = 9且Q [0] = 9。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数get_subarray()。这将需要P，Q，交换
N：= P的大小
index：=一个新映射
差：= 0，j：= 0
index [0]：=一对像(-1,-1)
对于0到N范围内的i，执行
如果交换是正确的，那么
除此以外，
返回
idx：=索引[Q [j]-P [i]]
显示从idx [1] +1到j的所有值
显示从idx [0] +1到i的所有值
idx：=索引[Q [j]-P [i]]
显示P的从idx [0] +1到i的所有值
显示从idx [1] +1到j的所有值
j：= j + 1
当Q [j] <P [i]时，
差异：= Q [j]-P [i]
如果索引中存在差异，则
索引[差异]：=(i,j)
显示-1
从主要方面，执行以下操作-
使用它们的累计和更新P和Q
N：= P的大小
如果Q [N-1]> P [N-1]，则
get_subarray(P,Q,False)
除此以外，
get_subarray(Q,P,True)
例
让我们看下面的实现以更好地理解-
def show_res(x, y, num):print("Indices of array", num, ":", end = " ")
for i in range(x, y):
print(i, end = ", ")
print(y)
def get_subarray(P, Q, swap):
N = len(P)
index = {}
difference, j = 0, 0
index[0] = (-1, -1)
for i in range(0, N):
while Q[j] < P[i]:
j += 1
difference = Q[j] - P[i]
if difference in index:
if swap:
idx = index[Q[j] - P[i]]
show_res(idx[1] + 1, j, 1)
show_res(idx[0] + 1, i, 2)
else:
idx = index[Q[j] - P[i]]
show_res(idx[0] + 1, i, 1)
show_res(idx[1] + 1, j, 2)
return
index[difference] = (i, j)
print(-1)
def cumsum(arr):
n = len(arr)
for i in range(1, n):
arr[i] += arr[i - 1]
P = [2, 3, 4, 5, 6]
Q = [9, 3, 2, 6, 5]
cumsum(P)
cumsum(Q)
N = len(P)
if Q[N - 1] > P[N - 1]:
get_subarray(P, Q, False)
else:
get_subarray(Q, P, True)
输入项
[2, 3, 4, 5, 6],[9, 3, 2, 6, 5]
输出结果
Indices of array 1 : 0, 1, 2Indices of array 2 : 0
以上是 从给定的两个数组中查找子数组，以便它们在Python中的总和相等 的全部内容， 来源链接： utcz.com/z/359779.html
