প্রদত্ত দুটি অ্যারে থেকে সাব-অ্যারে খুঁজুন যেমন তাদের পাইথনে সমান যোগফল রয়েছে

ধরুন আমাদের দুটি অ্যারে আছে 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 :=একটি নতুন মানচিত্র

• পার্থক্য :=0, j :=0

• index[0] :=একটি জোড়ার মত (-1, -1)

• i 0 থেকে N রেঞ্জের জন্য, করুন

  • যখন Q[j]

    • j :=j + 1

  • পার্থক্য :=Q[j] - P[i]

  • যদি সূচকে পার্থক্য থাকে, তাহলে

    • যদি swap ture হয়, তাহলে

      • 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 পর্যন্ত সমস্ত মান প্রদর্শন করুন

    • ফেরত

  • সূচক [পার্থক্য] :=(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