在 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 的大小
索引 := 一个新的映射
差异 := 0,j := 0
index[0] := 一对类似 (-1, -1)
对于 0 到 N 范围内的 i,执行
当 Q[j] < P[i],执行
j := j + 1
difference := Q[j] - P[i]
如果索引中存在差异,则
如果交换为真,则
idx := index[Q[j] - P[i]]
显示 P 的从 idx[1] + 1 到 j 的所有值
显示 Q 的从 idx[0] + 1 到 i 的所有值
否则,
idx := index[Q[j] - P[i]]
显示 P 的从 idx[0] + 1 到 i 的所有值
显示 Q 的从 idx[1] + 1 到 j 的所有值
返回
index[difference] := (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, 2 Indices of array 2 : 0
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

