数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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、swap
N := P 的大小
index := 一个新的映射
difference := 0，j := 0
index[0] := 一对类似于 (-1, -1)
对于 i 的范围从 0 到 N，执行以下操作：
当 Q[j] < P[i] 时，执行以下操作：
j := j + 1
difference := Q[j] - P[i]
如果 index 中存在 difference，则执行以下操作：
如果 swap 为真，则执行以下操作：
idx := index[Q[j] - P[i]]
显示从 idx[1] + 1 到 j 的所有 P 值
显示从 idx[0] + 1 到 i 的所有 Q 值
否则，执行以下操作：
idx := index[Q[j] - P[i]]
显示从 idx[0] + 1 到 i 的所有 P 值
显示从 idx[1] + 1 到 j 的所有 Q 值
返回
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
323 次查看
