পাইথনে দুটি অ্যারে থেকে সমান সম্বলিত সাবঅ্যারে খুঁজে বের করা

দুটি অ্যারে P এবং Q দেওয়া আছে (আকার N, উপাদান ১ থেকে N)। এমন সাবঅ্যারে খুঁজে বের করতে হবে যারা সমান যোগফল রাখে। তাদের ইনডেক্স ফেরত দিন। না থাকলে -1।

উদাহরণ

ইনপুট: P = [2, 3, 4, 5, 6], Q = [9, 3, 2, 6, 5]

আউটপুট: P-এর ইনডেক্স 0,1,2 (যোগফল ৯) এবং Q-এর ইনডেক্স ০ (যোগফল ৯)

সমাধানের পদ্ধতি

1. প্রতিটি অ্যারের কামুলেটিভ সম (cumulative sum) বানান।
2. দুটি পয়েন্টার টেকনিক ব্যবহার করুন।
3. P[i] এবং Q[j] এর পার্থক্য (difference) ট্র্যাক করুন।
4. একই পার্থক্য دوبার পাওয়া গেলে, তাদের মাঝপথের সাবঅ্যারে সমান যোগফল দেবে।
5. হ্যাশ ম্যাপ (hash map) দিয়ে পার্থক্য ও ইনডেক্স স্টোর করুন।

পাইথন কোড

def show_res(x, y, num):
    print(f"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 = 0
    j = 0
    index[0] = (-1, -1)
    
    for i in range(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