पायथन में दो दिए गए ऐरे से सब-अरे खोजें जिनका योग समान हो

मान लीजिए हमारे पास दो ऐरे 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]

  • यदि difference index में मौजूद है, तो:

    • यदि 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