題目出處
1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
難度
medium
題目分類
Array, Hash Table, Binary Search, Dynamic Programming, Sliding Window
2026-09-18 一刷
個人範例程式碼 - 一刷 (2026/09/18)
class Solution:
def minSumOfLengths(self, arr: List[int], target: int) -> int:
INF = float('inf')
dp = [INF] * len(arr) # best ans from head to current idx
final_ans = INF
# sliding window
left = 0
sum_in_window = 0
for right in range(len(arr)):
sum_in_window += arr[right]
# don't need to handle equal since there is not value <= 0
while sum_in_window > target:
sum_in_window -= arr[left]
left += 1
if sum_in_window == target:
ans = right - left + 1
# update DP and possible final ans
dp[right] = min(dp[right], ans)
# non overlap handle: left-1
if left > 0: # edge case = [target] target
final_ans = min(final_ans, dp[left-1] + ans)
# update DP
if right > 0: # prevent dp[-1]
dp[right] = min(dp[right], dp[right-1])
return -1 if final_ans == INF else final_ans
算法說明
主要流程
需要一個 DP，用於紀錄左側最好的答案，
具體來說，假設我們找到範圍 (C, D) 和可以符合目標 target
我們要從 B 位置，也就是 C 的前一個 (才沒有 overlap)，往前找最好的組合
示意：[A…B C… D]
也就是說，我們找到的是當下的第二組最短答案，然後透過 DP 去找到前面 B 位置前的最佳解。
這樣這兩個長度的總和就是最佳解。
DP 更新部分
至於 DP 的更新部分，找到答案的當下 DP[i] = min(DP[i], ans)
每一輪的更新，檢查與前一個位置比是否也為最佳 DP[i] = min(DP[i], DP[i-1])
註：小技巧記憶 INF = float(‘inf’) 宣告一個浮點數極大值
Time Complexity
O(n) # 實際約為 O(2n)，代表的意義是 left 與 right 各自移動一輪
Space Complexity
O(n) # dp = [INF] * len(arr)
Boundary conditions
edge:
- [3], target = 3，也就是只有一個值剛好就是 target 的情況，用 left > 0 來排除
- [7, 3, 4, 7] 要透過這個例子知道應該要先處理左邊界 (while 部分) 再來更新 DP