หาสับอาร์เรย์จากสองอาร์เรย์ที่มีผลรวมเท่ากันใน Python

สมมติว่าเรามีอาร์เรย์ P และ Q ขนาด N เก็บตัวเลข 1 ถึง N ต้องการหาสับอาร์เรย์จากทั้งสองอาร์เรย์ที่มีผลรวมเท่ากัน คืนค่าดัชนี หากไม่มี คืนค่า -1

เช่น P = [2, 3, 4, 5, 6], Q = [9, 3, 2, 6, 5] ผลลัพธ์: P[0..2] = 9, Q[0] = 9

ขั้นตอนการแก้ปัญหา (Prefix Sum + Hash Map)

1. แปลง P และ Q เป็น prefix sum
2. ใช้ two-pointer และแผนที่เก็บความต่างของ prefix sum
3. เมื่อเจอความต่างซ้ำ แสดงว่ามีสับอาร์เรย์ผลรวมเท่ากัน

ตัวอย่างโค้ด Python

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 = {0: (-1, -1)}
    diff = j = 0
    for i in range(N):
        while Q[j] < P[i]:
            j += 1
        diff = Q[j] - P[i]
        if diff in index:
            idx = index[diff]
            if swap:
                show_res(idx[1] + 1, j, 1)
                show_res(idx[0] + 1, i, 2)
            else:
                show_res(idx[0] + 1, i, 1)
                show_res(idx[1] + 1, j, 2)
            return
        index[diff] = (i, j)
    print(-1)

def cumsum(arr):
    for i in range(1, len(arr)):
        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