পাইথনে বাইনারি লিস্টে নির্দিষ্ট সমের সাবলিস্ট কাউন্ট করা

একটি বাইনারি লিস্ট (০ এবং ১) এবং টার্গেট k দেওয়া আছে। সম k হয় এমন সাবলিস্টের সংখ্যা বের করুন।

ইনপুট উদাহরণ

nums = [1, 0, 0, 1, 1, 1, 0, 1]
k = 3

আউটপুট: 8

অ্যালগরিদম

প্রিফিক্স সম + হ্যাশแมপ ব্যবহার করুন। sums[prefix_sum] = সেই প্রিফিক্স সম কতবার আসেছে। প্রতিটি উপাদানের জন্য sums[curr_sum - k] যোগ করুন।

পাইথন কোড

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

# টেস্ট
print(solve([1,0,0,1,1,1,0,1], 3))  # 8

ব্যাখ্যা

সাবঅ্যারে সম = prefix[j] - prefix[i] = k। তাই prefix[i] = prefix[j] - k। হ্যাশแมপ দিয়ে O(n) টাইমে সমাধান।