Cho mảng arr và target. Tìm hai mảng con không giao nhau mà mỗi mảng con có tổng = target. Nếu nhiều đáp án, chọn cặp có tổng độ dài nhỏ nhất. Trả về tổng độ dài nhỏ nhất, hoặc -1 nếu không tồn tại.
Ví dụ: arr = [5,2,6,3,2,5], target = 5. Các mảng con tổng 5: [5], [3,2], [5]. Chọn hai mảng con độ dài 1 → tổng độ dài = 2.
Thuật toán giải quyết (Prefix Sum + DP)
- ans := vô cực, best[i] := độ dài nhỏ nhất của mảng con kết thúc tại hoặc trước i có tổng = target.
- prefix := 0, latest := {0: -1} (lưu chỉ số mới nhất của mỗi prefix sum).
- Duyệt i, x trong arr:
- prefix += x.
- Nếu prefix - target trong latest: ii = latest[prefix-target]. Mảng con (ii+1..i) có tổng target, độ dài = i-ii.
- Nếu ii ≥ 0: ans = min(ans, i-ii + best[ii]) (ghép với mảng con tốt nhất trước ii).
- best[i] = i-ii.
- best[i] = min(best[i-1], best[i]) (lan truyền giá trị tốt nhất).
- latest[prefix] = i.
- Trả về ans nếu ans < vô cực, ngược lại -1.
Ví dụ triển khai
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))Đầu vào
[5,2,6,3,2,5], 5
Đầu ra
2