दिए गए दो सरणियों से उप-सरणी खोजें जैसे कि उनके पास पायथन में समान योग है

मान लीजिए कि हमारे पास दो सरणियाँ 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, जे:=0

• index[0] :=एक जोड़ी जैसे (-1, -1)

• मेरे लिए 0 से N की सीमा में, करें

  • जबकि Q[j]

    • जे:=जे + 1

  • अंतर:=क्यू[जे] - पी[i]

  • यदि सूचकांक में अंतर मौजूद है, तो

    • अगर अदला-बदली सही है, तो

      • आईडीएक्स:=सूचकांक [क्यू [जे] - पी [i]]

      • P के लिए idx[1] + 1 से j तक सभी मान प्रदर्शित करें

      • Q

        . के लिए idx[0] + 1 से i तक के सभी मान प्रदर्शित करें

    • अन्यथा,

      • आईडीएक्स:=सूचकांक [क्यू [जे] - पी [i]]

      • P के लिए idx[0] + 1 से i तक के सभी मान प्रदर्शित करें

      • Q

        . के लिए idx[1] + 1 से j तक सभी मान प्रदर्शित करें

    • वापसी

  • अनुक्रमणिका [अंतर] :=(i, j)

• डिस्प्ले -1

• मुख्य विधि से, निम्न कार्य करें -

• P और Q को उनकी संचयी राशि का उपयोग करके अपडेट करें

• N:=P का आकार

• अगर क्यू [एन -1]> पी [एन -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