ধরুন আমাদের 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]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- সমস্য :=একটি মানচিত্রে প্রাথমিকভাবে কী 0 এর জন্য ভ্যালি 1 থাকে
- r_sum :=0
- উত্তর :=0
- সংখ্যায় প্রতিটি x এর জন্য, করুন
- r_sum :=r_sum + x
- উত্তর :=উত্তর + (অর্থ [r_sum - k] যদি (r_sum - k) থাকে, অন্যথায় 0)
- সম্পর্ক[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
