Tìm mảng con từ hai mảng đã cho sao cho chúng có tổng bằng nhau trong Python

Giả sử chúng ta có hai mảng P và Q có kích thước là N, chúng chứa các số từ 1 đến N. Chúng ta phải tìm các mảng con từ các mảng đã cho để chúng có tổng bằng nhau. Cuối cùng trả về các chỉ số của các mảng con như vậy. Nếu không có giải pháp nào, hãy trả về -1.

Vì vậy, nếu đầu vào là P =[2, 3, 4, 5, 6], Q =[9, 3, 2, 6, 5], thì đầu ra sẽ là Chỉ số ở đầu tiên mảng:0, 1, 2 và các chỉ số trong mảng thứ hai:0, do đó P [0..2] =2 + 3 + 4 =9 và Q [0] =9.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm get_subarray (). Điều này sẽ lấy P, Q, hoán đổi

• N:=kích thước của P

• index:=một bản đồ mới

• sự khác biệt:=0, j:=0

• index [0]:=một cặp như (-1, -1)

• đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện

  • trong khi Q [j]

    • j:=j + 1

  • sự khác biệt:=Q [j] - P [i]

  • nếu có sự khác biệt trong chỉ mục, thì

    • nếu hoán đổi là chắc chắn, thì

      • idx:=index [Q [j] - P [i]]

      • hiển thị tất cả các giá trị từ idx [1] + 1 đến j cho P

      • hiển thị tất cả các giá trị từ idx [0] + 1 đến i cho Q

    • nếu không,

      • idx:=index [Q [j] - P [i]]

      • hiển thị tất cả các giá trị từ idx [0] + 1 đến i cho P

      • hiển thị tất cả các giá trị từ idx [1] + 1 đến j cho Q

    • trở lại

  • chỉ số [chênh lệch]:=(i, j)

• hiển thị -1

• Từ methood chính, hãy làm như sau -

• Cập nhật P và Q bằng cách sử dụng tổng tích lũy của chúng

• N:=kích thước của P

• nếu Q [N - 1]> P [N - 1] thì

  • get_subarray (P, Q, False)

• nếu không,

  • get_subarray (Q, P, True)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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)

Đầu vào

[2, 3, 4, 5, 6],[9, 3, 2, 6, 5]

Đầu ra

Indices of array 1 : 0, 1, 2
Indices of array 2 : 0