দুটি ননওভারল্যাপিং সাবলিস্টের দৈর্ঘ্যের যোগফল খুঁজে বের করার প্রোগ্রাম যার যোগফল পাইথনে দেওয়া হয়েছে

ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা আছে এবং আরেকটি মান k, আমাদেরকে সংখ্যার মধ্যে দুটি ননওভারল্যাপিং সাবলিস্ট খুঁজে বের করতে হবে যার যোগফল k, এবং আমাদের তাদের দৈর্ঘ্যের যোগফল খুঁজে বের করতে হবে। যখন দুটি সম্ভাব্য সাবলিস্ট থাকে, তখন আমাদের দুটি ক্ষুদ্রতম সাবলিস্টের দৈর্ঘ্যের যোগফল খুঁজে বের করতে হবে। যদি আমরা উত্তর খুঁজে না পাই, −1 ফেরত দিন।

সুতরাং, ইনপুট যদি nums =[7, 10, −2, −1, 4, 3] k =7 এর মতো হয়, তাহলে আউটপুট হবে 3, যেমন আমরা [7] এবং [4, 3] এর মতো সাবলিস্ট বাছাই করি। . আমরা [10, −2, −1] বাছাই করিনি কারণ এটি দীর্ঘ।

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

N :=A
এর আকার
উপসর্গ :=আকারের N, এবং অসীম দিয়ে পূরণ করুন
শেষ :=কী 0 {0:−1}
এর জন্য −1 মান সহ একটি মানচিত্র
s :=0
i 0 থেকে N রেঞ্জের জন্য, করুন
- s :=s + A[i]
- উপসর্গ[i] :=i − last[s − target], যদি না পাওয়া যায় সেট −infinity
- শেষ [s] :=i
1 থেকে N রেঞ্জের জন্য, করুন
- উপসর্গ[i] :=সর্বনিম্ন উপসর্গ[i], উপসর্গ[i − 1]
প্রত্যয় :=আকারের N, এবং অসীম দিয়ে পূরণ করুন
শেষ :=কী 0 {0:N}
এর জন্য N মান সহ একটি মানচিত্র
s :=0
N − 1 থেকে −1 রেঞ্জের i জন্য, 1 দ্বারা হ্রাস করুন, করুন
- s :=s + A[i]
- প্রত্যয়[i] :=last[s − target] (যদি পাওয়া না যায় সেট ইনফিনিটি) − i
- শেষ [s] :=i
N − 2 থেকে −1 পরিসরে i জন্য, 1 দ্বারা হ্রাস করুন, করুন
- প্রত্যয়[i] :=সর্বনিম্ন প্রত্যয়[i] এবং প্রত্যয়[i + 1]
উত্তর :=0 থেকে N − 1 পরিসরের প্রতিটি i-এর জন্য সর্বনিম্ন উপসর্গ[i] + প্রত্যয়[i + 1]
উত্তর দিন যদি ans

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, A, target):
      INF = float("inf")
      N = len(A)
      prefix = [INF] * N
      last = {0: −1}
      s = 0
      for i in range(N):
         s += A[i]
         prefix[i] = i − last.get(s − target, −INF)
         last[s] = i
      for i in range(1, N):
         prefix[i] = min(prefix[i], prefix[i − 1])
      suffix = [INF] * N
      last = {0: N}
      s = 0
      for i in range(N − 1, −1, −1):
         s += A[i]
         suffix[i] = last.get(s − target, INF) − i
         last[s] = i
      for i in range(N − 2, −1, −1):
         suffix[i] = min(suffix[i], suffix[i + 1])
      ans = min(prefix[i] + suffix[i + 1] for i in range(N − 1))
      return ans if ans < INF else −1
ob = Solution()
nums = [7, 10, −2, −1, 4, 3]
k = 7
print(ob.solve(nums, k))

ইনপুট

[7, 10, −2, −1, 4, 3], 7