पायथन में बाइनरी सूची में योग के साथ उपन्यासकारों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास 0s या 1s के साथ एक बाइनरी सूची है। हमारे पास k नामक एक अन्य इनपुट भी है, हमें उन सबलिस्ट्स की संख्या ज्ञात करनी है जिनका योग k के समान है।

इसलिए, यदि इनपुट संख्या =[1, 0, 0, 1, 1, 1, 0, 1] k =3 की तरह है, तो आउटपुट 8 होगा क्योंकि सबलिस्ट [1,0,0,1,1] हैं ], [0,0,1,1,1], [0,0,1,1,1,0], [0,1,1,1], [0,1,1,1,0], [1,1,1], [1,1,1,0] [1,1,0,1]।

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

• sums :=एक मानचित्र में प्रारंभ में कुंजी 0 के लिए valye 1 होता है
• r_sum :=0
• उत्तर:=0
• अंकों में प्रत्येक x के लिए, करें
  • r_sum :=r_sum + x
  • उत्तर:=उत्तर + (योग [r_sum - k] यदि (r_sum - k) मौजूद है, अन्यथा 0)
  • sums[r_sum] :=1 + (योग [r_sum - k] यदि (r_sum - k) मौजूद है, अन्यथा 0)
• वापसी उत्तर

उदाहरण

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

def solve(nums, k):
   sums = {0: 1}
   r_sum = 0
   ans = 0

   for x in nums:
      r_sum += x
      ans += sums.get(r_sum - k, 0)
      sums[r_sum] = sums.get(r_sum, 0) + 1

   return ans

nums = [1, 0, 0, 1, 1, 1, 0, 1]
k = 3
print(solve(nums, k))

इनपुट

[1, 0, 0, 1, 1, 1, 0, 1], 3

आउटपुट

8