在 Python 中从给定的两个数组中找出子数组,使得它们的总和相等

pythonserver side programmingprogramming更新于 2025/9/27 5:32:17

假设我们有两个数组 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

相关文章


有用资源