ค้นหาอาร์เรย์ย่อยจากสองอาร์เรย์ที่กำหนดเพื่อให้มีผลรวมเท่ากันในPython

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

ดังนั้น หากอินพุตเป็นเช่น P =[2, 3, 4, 5, 6], Q =[9, 3, 2, 6, 5] ผลลัพธ์จะเป็นดัชนีก่อน array :0, 1, 2 และดัชนีในอาร์เรย์ที่สอง:0, ดังนั้น P[0..2] =2 + 3 + 4 =9 และ Q[0] =9

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน get_subararay() นี่จะใช้เวลา P, Q, สลับ

• N :=ขนาดของพี

• index :=แผนที่ใหม่

• ความแตกต่าง :=0, j :=0

• index[0] :=คู่ที่ชอบ (-1, -1)

• สำหรับผมอยู่ในช่วง 0 ถึง N ทำ

  • ในขณะที่ Q[j]

    • เจ :=เจ + 1

  • ความแตกต่าง :=Q[j] - P[i]

  • หากมีความแตกต่างในดัชนีแล้ว

    • ถ้า swap เป็น ture แล้ว

      • 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

    • กลับ

  • ดัชนี[แตกต่าง] :=(i, j)

• แสดง -1

• จากเมธอดหลัก ให้ทำดังนี้ −

• อัปเดต P และ Q โดยใช้ผลรวมสะสม

• N :=ขนาดของพี

• ถ้า Q[N - 1]> P[N - 1] แล้ว

  • get_subarray(P, Q, เท็จ)

• มิฉะนั้น

  • get_subarray(Q, P, จริง)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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