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

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k, हमें दो गैर-अतिव्यापी उप-सूचियों को अंकों में खोजना होगा, जिनका योग k है, और हमें उनकी लंबाई का योग ज्ञात करना है। जब दो से अधिक संभावित उपन्यासकार हों, तो हमें दो सबसे छोटे उपन्यासकारों की लंबाई का योग ज्ञात करना होगा। अगर हमें जवाब नहीं मिल रहा है, तो -1 पर लौटें।

इसलिए, यदि इनपुट nums =[7, 10, −2, −1, 4, 3] k =7 जैसा है, तो आउटपुट 3 होगा, जैसा कि हम [7] और [4, 3] जैसे उप-सूचियों को चुनते हैं। . हमने [10, −2, −1] को नहीं चुना क्योंकि यह लंबा है।

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

N:=A का आकार
उपसर्ग :=आकार N का, और अनंत से भरें
अंतिम :=कुंजी 0 के लिए −1 मान वाला नक्शा {0:−1}
एस:=0
मेरे लिए 0 से N की सीमा में, करें
- एस:=एस + ए[i]
- उपसर्ग [i] :=i - अंतिम [s - लक्ष्य], यदि सेट नहीं मिला - अनंतता
- अंतिम [s] :=मैं
1 से N की श्रेणी में i के लिए, करें
- उपसर्ग [i] :=न्यूनतम उपसर्ग [i], उपसर्ग [i − 1]
प्रत्यय :=आकार N का, और अनंत से भरें
अंतिम:=कुंजी 0 के लिए मान N वाला नक्शा {0:N}
एस:=0
N − 1 से −1 की श्रेणी में i के लिए, 1 की कमी करें
- एस:=एस + ए[i]
- प्रत्यय [i] :=last[s - target] (यदि सेट अनंत नहीं मिला) - i
- अंतिम [s] :=मैं
मैं के लिए एन -2 से -1 की सीमा में, 1 की कमी, करो
- प्रत्यय [i]:=न्यूनतम प्रत्यय [i] और प्रत्यय [i + 1]
उत्तर:=न्यूनतम उपसर्ग [i] + प्रत्यय [i + 1] प्रत्येक i के लिए 0 से N - 1 तक की सीमा में
वापसी उत्तर यदि उत्तर <अनंतता अन्यथा -1

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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