Pythonで合計が等しくなるように、指定された2つの配列からサブ配列を検索します

サイズがNの2つの配列PとQがあり、それらは1からNまでの数値を保持しているとします。合計が等しくなるように、指定された配列からサブ配列を見つける必要があります。最後に、そのようなサブ配列のインデックスを返します。解決策がない場合は、-1を返します。

したがって、入力がP =[2、3、4、5、6]、Q =[9、3、2、6、5]の場合、出力は最初にインデックスになります配列：0、1、2および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の場合、実行

  • Q [j]

    • j：=j + 1

  • 違い：=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