একটি arr অ্যারে এবং target মান দেওয়া আছে। arr-এ থেকে দুটি নন-ওভারল্যাপিং সাবঅ্যারে খুঁজে বের করতে হবে যাতে প্রতিটির সম target-এর সমান হয়। যদি একাধিক সমাধান থাকে, তবে দুটি সাবঅ্যারের দৈর্ঘ্যের যোগফল ন্যূনতম হওয়া সমাধান বেছে নিতে হবে। ন্যূনতম দৈর্ঘ্য যোগফল ফেরত দিন, না পাওয়া গেলে -1 ফেরত দিন।
যেমন, arr = [5,2,6,3,2,5], target = 5 হলে আউটপুট ২। কারণ সম ৫ পাওয়া সাবঅ্যারেগুলো: [5], [3,2], [5]। এদের মধ্যে দুটির দৈর্ঘ্য ১+১=২ ন্যূনতম।
সমাধানের ধাপসমূহ
- ans := অসীম, best := arr-এর আকার অনুযায়ী অসীম দিয়ে ভরা লিস্ট
- prefix := 0, latest := {0: -1} (প্রিফিক্স সম -> ইনডেক্স ম্যাপ)
- arr-এর প্রতিটি ইনডেক্স i এবং মান x এর জন্য:
- prefix += x
- যদি (prefix - target) latest-এ থাকে, তবে ii := latest[prefix - target]
- যদি ii >= 0 হয়, তবে ans := min(ans, i - ii + best[ii])
- best[i] := i - ii
- যদি i != 0 হয়, তবে best[i] := min(best[i-1], best[i])
- latest[prefix] := i
- ans < 999999 হলে ans ফেরত দিন, অন্যথায় -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
