資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 Python 中查詢來自給定兩個陣列的子陣列，使得它們具有相等的和
假設我們有兩個陣列 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 := 一個新的對映
difference := 0，j := 0
index[0] := 一對類似於 (-1, -1)
對於 i 的範圍從 0 到 N，執行以下操作：
當 Q[j] < P[i] 時，執行以下操作：
j := j + 1
difference := Q[j] - P[i]
如果 index 中存在 difference，則執行以下操作：
如果 swap 為真，則執行以下操作：
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 值
返回
index[difference] := (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
323 次檢視
