पायथन में बाइनरी सूची में योग k वाले सबलिस्ट की संख्या खोजने का प्रोग्राम

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

इसलिए, यदि इनपुट है nums = [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 के लिए मान 1 हो
• r_sum := 0
• ans := 0
• nums में प्रत्येक x के लिए, करें:
  • r_sum := r_sum + x
  • ans := ans + (sums[r_sum - k] यदि (r_sum - k) मौजूद है, अन्यथा 0)
  • sums[r_sum] := 1 + (sums[r_sum] यदि मौजूद है, अन्यथा 0)
• ans लौटाएं

उदाहरण

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

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