Giả sử chúng ta có một mảng arr và một mục tiêu giá trị khác. Chúng ta phải tìm hai mảng con không chồng lên nhau của arr trong đó mỗi mảng có tổng bằng đích. Nếu có nhiều đáp án thì ta phải tìm một đáp án mà tổng độ dài của hai mảng con là nhỏ nhất. Chúng ta phải tìm tổng độ dài tối thiểu của hai mảng con bắt buộc, nếu không có mảng con như vậy thì trả về -1.
Vì vậy, nếu đầu vào giống như arr =[5,2,6,3,2,5] target =5, thì đầu ra sẽ là 2, có ba mảng con có tổng 5, chúng là [5], [3,2 ] và [5], bây giờ trong số đó chỉ có hai cái có kích thước nhỏ nhất.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ans:=infinity
-
best:=tạo một mảng có kích thước bằng arr và lấp đầy bằng vô cực
-
tiền tố:=0
-
mới nhất:=một bản đồ nơi lưu trữ -1 cho khóa 0
-
đối với mỗi chỉ mục i và giá trị x của arr, thực hiện
-
tiền tố:=prefix + x
-
nếu (tiền tố - đích) xuất hiện muộn nhất, thì
-
ii:=mới nhất [tiền tố - target]
-
nếu ii> =0, thì
-
ans:=tối thiểu ans và (i - ii + tốt nhất [ii])
-
-
tốt nhất [i]:=i - ii
-
-
nếu tôi khác 0, thì
-
[tiền tố] mới nhất:=i
-
-
-
trả về ans nếu ans <999999 nếu không thì -1
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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