পাইথন ব্যবহার করে লক্ষ্য সমষ্টি সহ দুটি নন-ওভারল্যাপিং সাব-অ্যারে খোঁজার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারের অ্যারে এবং আরেকটি ভ্যালু টার্গেট আছে। আমাদের arr-এর দুটি নন-ওভারল্যাপিং সাব-অ্যারে খুঁজে বের করতে হবে যেখানে প্রতিটির সমষ্টি লক্ষ্যের সমান। যদি একাধিক উত্তর থাকে, তাহলে আমাদের একটি উত্তর খুঁজতে হবে যেখানে দুটি সাব-অ্যারের দৈর্ঘ্যের যোগফল সবচেয়ে ছোট। আমাদের দুটি প্রয়োজনীয় সাব-অ্যারের দৈর্ঘ্যের ন্যূনতম যোগফল খুঁজে বের করতে হবে, যদি এমন কোন সাব-অ্যারে না থাকে তাহলে -1 ফেরত দিন।

সুতরাং, যদি ইনপুটটি হয় arr =[5,2,6,3,2,5] টার্গেট =5, তাহলে আউটপুট হবে 2 সেখানে যোগফল 5 সহ তিনটি সাবয়ারে রয়েছে, তারা হল [5], [3,2 ] এবং [5], এখন তাদের মধ্যে মাত্র দুটির আকার সবচেয়ে ছোট।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর :=অসীম

• সর্বোত্তম :=একটি অ্যারে তৈরি করুন যার আকার arr এর মতো এবং ইনফিনিটি দিয়ে পূরণ করুন

• উপসর্গ :=0

• সর্বশেষ :=একটি মানচিত্র যেখানে সংরক্ষণ করুন -1 কী 0

  এর জন্য

• প্রতিটি সূচক i এবং arr এর মান x এর জন্য, do

  • উপসর্গ :=উপসর্গ + x

  • যদি (উপসর্গ - লক্ষ্য) সর্বশেষে উপস্থিত থাকে, তাহলে

    • ii :=সর্বশেষ[উপসর্গ - লক্ষ্য]

    • যদি ii>=0 হয়, তাহলে

      • উত্তর :=সর্বনিম্ন উত্তর এবং (i - ii + সেরা[ii])

    • সেরা[i] :=i - ii

  • যদি আমি অ-শূন্য হয়, তাহলে

    • সর্বশেষ [উপসর্গ] :=i

• উত্তর দিন যদি উত্তর <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