สมมติว่าเรามีอาร์เรย์ arr และค่า target เราต้องหา subarray 2 อันที่ไม่ทับกัน ซึ่งแต่ละอันมีผลรวมเท่ากับ target หากมีหลายคำตอบ ให้เลือกคู่ที่ผลรวมของความยาวน้อยที่สุด คืนค่าผลรวมความยาวน้อยที่สุด ถ้าไม่มีคืน -1
เช่น arr = [5,2,6,3,2,5] target = 5 ผลลัพธ์คือ 2 เพราะมี subarray ผลรวม 5 ทั้งหมด 3 อันคือ [5], [3,2], [5] เลือก 2 อันที่สั้นที่สุดคือ [5] และ [5] ความยาวรวม = 2
ขั้นตอนการแก้ปัญหา
- ans = infinity, best = array ขนาด arr เติม infinity
- prefix = 0, latest = {0: -1} (เก็บ index ล่าสุดของแต่ละ prefix sum)
- วนลูป i, x ใน arr:
- prefix += x
- ถ้า (prefix - target) อยู่ใน latest:
- ii = latest[prefix - target] (index เริ่มต้นของ subarray ที่จบที่ i)
- ถ้า ii ≥ 0: ans = min(ans, i - ii + best[ii]) (รวมความยาว subarray ปัจจุบัน + subarray ก่อนหน้าสั้นที่สุดที่จบก่อน ii)
- best[i] = i - ii (ความยาว subarray ที่จบที่ i)
- ถ้า i > 0: best[i] = min(best[i-1], best[i]) (เก็บความยาวสั้นที่สุดจนถึง i)
- latest[prefix] = i
- คืน ans ถ้า 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
