資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用Python查詢兩個和為目標值的互不重疊子陣列的程式
假設我們有一個數組arr和另一個值target。我們必須找到arr的兩個互不重疊的子陣列，每個子陣列的和都等於target。如果有多個答案，那麼我們必須找到兩個子陣列長度之和最小的答案。如果不存在這樣的子陣列，則返回-1。
因此，如果輸入類似於arr = [5,2,6,3,2,5] target = 5，則輸出將為2，因為存在三個和為5的子陣列，它們是[5]，[3,2]和[5]，其中只有兩個子陣列具有最小的長度。
為了解決這個問題，我們將遵循以下步驟：
ans := 無窮大
best := 建立一個與arr大小相同的陣列，並用無窮大填充
prefix := 0
latest := 一個對映，其中鍵0的值為-1
對於arr的每個索引i和值x，執行：
prefix := prefix + x
如果(prefix - target)存在於latest中，則：
ii := latest[prefix - target]
如果ii >= 0，則：
ans := ans和(i - ii + best[ii])的最小值
best[i] := i - ii
如果i非零，則：
latest[prefix] := i
如果ans < 999999，則返回ans；否則返回-1
讓我們來看下面的實現以更好地理解：
示例
def solve(arr, target):
ans = 999999
best = [999999]*len(arr)
prefix = 0
latest = {0: -1}
for i, x in enumerate(arr):
prefix += x
if prefix - target in latest:
ii = latest[prefix - target]
if ii >= 0:
ans = min(ans, i - ii + best[ii])
best[i] = i - ii
if i: best[i] = min(best[i-1], best[i])
latest[prefix] = i
return ans if ans < 999999 else -1
arr = [5,2,6,3,2,5]
target = 5
print(solve(arr, target))輸入
[5,2,6,3,2,5], 5
輸出
2
更新於：2021年5月29日
瀏覽量：176
廣告