पायथन का उपयोग करके लक्ष्य योग के साथ दो गैर-अतिव्यापी उप-सरणी खोजने का कार्यक्रम

मान लीजिए कि हमारे पास गिरफ्तारी की एक सरणी और एक अन्य मूल्य लक्ष्य है। हमें एआर के दो गैर-अतिव्यापी उप-सरणी ढूंढनी है जहां प्रत्येक के पास लक्ष्य के बराबर योग है। यदि कई उत्तर हैं, तो हमें एक ऐसा उत्तर खोजना होगा जहां दो उप-सरणी की लंबाई का योग सबसे छोटा हो। हमें दो आवश्यक उप-सरणी की लंबाई का न्यूनतम योग खोजना होगा, यदि ऐसा कोई उप-सरणी नहीं है तो -1 लौटाएं।

इसलिए, यदि इनपुट एआर =[5,2,6,3,2,5] लक्ष्य =5 जैसा है, तो आउटपुट 2 होगा, योग 5 के साथ तीन उप-सरणी हैं, वे हैं [5], [3,2 ] और [5], अब उनमें से केवल दो का आकार सबसे छोटा है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• उत्तर:=अनंत

• सर्वोत्तम:=एक सरणी बनाएं जिसका आकार एआर के समान हो और अनंत से भर जाए

• उपसर्ग :=0

• नवीनतम:=एक नक्शा जहां कुंजी 0 के लिए -1 स्टोर करें

• प्रत्येक अनुक्रमणिका i और arr के मान x के लिए, करें

  • उपसर्ग :=उपसर्ग + x

  • अगर (उपसर्ग - लक्ष्य) नवीनतम में मौजूद है, तो

    • ii:=नवीनतम[उपसर्ग - लक्ष्य]

    • अगर ii>=0, तो

      • Ans :=न्यूनतम उत्तर और (i - ii + best[ii])

    • सर्वोत्तम [i] :=i - ii

  • अगर मैं शून्य नहीं हूं, तो

    • नवीनतम [उपसर्ग] :=मैं

• उत्तर दें यदि उत्तर <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