C++-এ Subarray Sum Equals K

এই সমস্যায় একটি পূর্ণসংখ্যার অ্যারে এবং ইন্টিজার k দেওয়া থাকলে, যোগফল k হওয়া কতটি কন্টিগুয়াস সাবঅ্যারে আছে তা বের করতে হবে।

উদাহরণ: nums = [1,1,1], k=2 -> আউটপুট 2 (সাবঅ্যারে: [1,1] দুবার)।

সমাধানের পদ্ধতি (Prefix Sum + Hash Map)

prefixSum = 0, ans = 0।
map[0] = 1 (খালি প্রিফিক্স সাম ০)।
প্রতিটি এলিমেন্ট num এর জন্য:
- prefixSum += num।
- যদি map-এ prefixSum - k থাকে, তবে ans += map[prefixSum - k]।
- map[prefixSum]++।

উদাহরণ (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixCount;
        prefixCount[0] = 1;
        int prefixSum = 0, ans = 0;
        for (int num : nums) {
            prefixSum += num;
            if (prefixCount.count(prefixSum - k))
                ans += prefixCount[prefixSum - k];
            prefixCount[prefixSum]++;
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 1, 1};
    cout << ob.subarraySum(v, 2);
    return 0;
}

ইনপুট

[1,1,1] 2

আউটপুট

সংশোধন: মূল কোডে sums[-temp]++ ছিল, যা ভুল (নেগেটিভ কি)। সঠিকভাবে prefixCount[prefixSum]++ করা উচিত।