資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢和為給定值的兩段不相交子列表的長度之和
假設我們有一個名為nums的數字列表和另一個值k，我們必須在nums中找到兩個不相交的子列表，其和為k，並且我們必須找到它們的長度之和。當存在兩個以上可能的子列表時，我們必須找到兩個最短子列表的長度之和。如果找不到答案，則返回-1。
因此，如果輸入類似於nums = [7, 10, -2, -1, 4, 3] k = 7，則輸出將為3，因為我們選擇子列表[7]和[4, 3]。我們沒有選擇[10, -2, -1]，因為這個更長。
為了解決這個問題，我們將遵循以下步驟：
N := A的大小
prefix := 大小為N的陣列，並用無窮大填充
last := 一個鍵值為0時值為-1的對映 {0: -1}
s := 0
對於範圍0到N中的i，執行：
s := s + A[i]
prefix[i] := i - last[s - target]，如果找不到則設定為負無窮大
last[s] := i
對於範圍1到N中的i，執行：
prefix[i] := prefix[i] 和 prefix[i - 1] 的最小值
suffix := 大小為N的陣列，並用無窮大填充
last := 一個鍵值為0時值為N的對映 {0: N}
s := 0
對於範圍N - 1到-1中的i（遞減），執行：
s := s + A[i]
suffix[i] := last[s - target] - i （如果找不到則設定為無窮大）
last[s] := i
對於範圍N - 2到-1中的i（遞減），執行：
suffix[i] := suffix[i] 和 suffix[i + 1] 的最小值
ans := 對於範圍0到N - 1中的每個i，prefix[i] + suffix[i + 1] 的最小值
如果ans < 無窮大，則返回ans；否則返回-1
讓我們看看下面的實現來更好地理解：
示例
class Solution:
def solve(self, A, target):
INF = float("inf")
N = len(A)
prefix = [INF] * N
last = {0: −1}
s = 0
for i in range(N):
s += A[i]
prefix[i] = i − last.get(s − target, −INF)
last[s] = i
for i in range(1, N):
prefix[i] = min(prefix[i], prefix[i − 1])
suffix = [INF] * N
last = {0: N}
s = 0
for i in range(N − 1, −1, −1):
s += A[i]
suffix[i] = last.get(s − target, INF) − i
last[s] = i
for i in range(N − 2, −1, −1):
suffix[i] = min(suffix[i], suffix[i + 1])
ans = min(prefix[i] + suffix[i + 1] for i in range(N − 1))
return ans if ans < INF else −1
ob = Solution()
nums = [7, 10, −2, −1, 4, 3]
k = 7
print(ob.solve(nums, k))輸入
[7, 10, −2, −1, 4, 3], 7
輸出
3
95 次瀏覽
