สมมติว่าเรามีอาร์เรย์ของ arr และเป้าหมายค่าอื่น เราต้องหาอาร์เรย์ย่อยที่ไม่ทับซ้อนกันสองอาร์เรย์ของ arr โดยที่แต่ละอาร์เรย์มีผลรวมเท่ากับเป้าหมาย หากมีหลายคำตอบ เราก็ต้องหาคำตอบโดยที่ผลรวมของความยาวของอาร์เรย์ย่อยทั้งสองมีค่าน้อยที่สุด เราต้องหาผลรวมต่ำสุดของความยาวของอาร์เรย์ย่อยที่จำเป็นทั้งสอง หากไม่มีอาร์เรย์ย่อยดังกล่าว ให้คืนค่า -1
ดังนั้น ถ้าอินพุตเป็นเหมือน arr =[5,2,6,3,2,5] เป้าหมาย =5 ผลลัพธ์จะเป็น 2 มีอาร์เรย์ย่อยสามชุดที่มีผลรวม 5 คือ [5], [3,2 ] และ [5] ตอนนี้มีเพียง 2 ตัวเท่านั้นที่มีขนาดเล็กที่สุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ตอบ :=อินฟินิตี้
-
ดีที่สุด :=สร้างอาร์เรย์ที่มีขนาดเท่ากับ arr และเติมอินฟินิตี้
-
คำนำหน้า :=0
-
ล่าสุด :=แผนที่ที่เก็บ -1 สำหรับคีย์ 0
-
สำหรับแต่ละดัชนี i และค่า x ของ arr ทำ
-
คำนำหน้า :=คำนำหน้า + x
-
ถ้า (คำนำหน้า - เป้าหมาย) มีอยู่ในเวอร์ชันล่าสุดแล้ว
-
ii :=ล่าสุด[คำนำหน้า - เป้าหมาย]
-
ถ้า ii>=0 แล้ว
-
ans :=ขั้นต่ำของ ans และ (i - ii + best[ii])
-
-
ดีที่สุด[i] :=i - ii
-
-
ถ้าฉันไม่เป็นศูนย์แล้ว
-
ล่าสุด[คำนำหน้า] :=ฉัน
-
-
-
ส่งคืน ans if ans <999999 มิฉะนั้น -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
