1.3 Prefix Sum

Demo: Subarray Sum Equals K — LC 560 (Medium)

Statement (Demo): integer array nums ও integer k দেওয়া — যোগফল k এমন contiguous subarray-এর মোট সংখ্যা বের করুন। (negative number থাকতে পারে।) উদাহরণ: nums=[1,1,1], k=2 → 2 | ⚡ n ≤ 2×10⁴, -1000 ≤ nums[i] ≤ 1000

Approach: চলতে চলতে running prefix sum রাখুন। sum[i..j] = k মানে prefix[j] - prefix[i-1] = k, অর্থাৎ আগে কোথাও prefix - k মানের prefix দেখা গেছে কি না — সেটা hashmap-এ count সহ রাখলেই হয়। (negative number থাকলেও কাজ করে, যেখানে sliding window ব্যর্থ।)

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]); // খালি prefix
  let sum = 0,
    count = 0;
  for (const x of nums) {
    sum += x;
    count += seen.get(sum - k) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}

Complexity: Time O(n), Space O(n)