Problem link ও উৎস
- **Original source:** Classic prefix-sum + hash-map exercise
- **Platform:** LeetCode —
- **Topic:** array / prefix sums / hash map
- **Difficulty:** Medium
- **Pattern:** prefix sums + hash map (running prefix-এর complement খোঁজা)
- **Basic idea inherited from:** Two Sum-এর complement + prefix sums — "current prefix − k সমান কোনো prefix কি আগে দেখেছি?"
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` (negative-ও থাকতে পারে) আর একটা সংখ্যা `k` দেওয়া। এমন কয়টা **পরপর থাকা (contiguous) subarray** আছে যাদের element-গুলোর যোগফল ঠিক `k`, সেটা গুনতে হবে। শুধু সংখ্যা (count) ফেরত দাও।
```text
nums = [1, 1, 1], k = 2
sum 2 হয়: [1,1] (index 0-1) আর [1,1] (index 1-2) -> count = 2
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 1, 1], k=2 -> 2
Input : [1, 2, 3], k=3 -> 2 ([1,2] আর [3])
Edge case 1 (negative + 0): [1, -1, 0], k=0 -> 3 ([1,-1], [0], [1,-1,0])
Edge case 2 (লম্বা mix): [3,4,7,2,-3,1,4,2], k=7 -> 4
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি হাঁটতে হাঁটতে "শুরু থেকে এ পর্যন্ত মোট কত" টুকছ। কেউ যদি জানতে চায় "ঠিক `k` দূরত্বের কয়টা টুকরো আছে", তুমি প্রতি জায়গায় ভাবো — "এর `k` আগে আমি যে মোট-মান-এ ছিলাম, সেটা ক'বার ছুঁয়েছি?" প্রতিটা সেই পুরনো মুহূর্ত একটা ঠিক-`k` টুকরোর শুরু।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Two Sum-এর complement thinking** আর **prefix sums** মিলিয়ে দেয়। prefix sum-এ `sum(i..j) = prefix[j] - prefix[i-1]`; তাই `sum = k` মানে `prefix[i-1] = prefix[j] - k`। অর্থাৎ চলতে চলতে প্রশ্ন করো — "current prefix − k সমান কোনো prefix কি আগে দেখেছি?" — ঠিক Two Sum-এর "complement আগে দেখেছি?" এর মতো। গভীরভাবে [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা subarray `(i..j)`-এর sum হলো `prefix[j] - prefix[i-1]`। সেটা `k` হওয়া মানে `prefix[i-1] = prefix[j] - k`। তাই প্রতিটা j-তে দরকার "এর আগে কতবার `prefix[j] - k` মান-এর prefix দেখা গেছে" — প্রতিটা এমন পুরনো prefix একটা valid subarray-র শুরু। count জমিয়ে রাখা prefix-এর frequency map থেকে আসে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **hash map (dict)** `seen`, যেখানে key = এ পর্যন্ত দেখা prefix sum, value = সেটা কতবার এসেছে। সাথে দুটো scalar — `running` (চলমান prefix sum) আর `count`। শুরুতে `seen = {0: 1}` (খালি prefix একবার ধরা)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Dict-এর lookup/insert average **O(1)**, তাই "এই prefix কতবার আগে দেখেছি" এক pass-এ জানা যায়। prefix sum negative-ও হতে পারে বলে fixed-size array না নিয়ে dict নেওয়াই সঠিক। এক pass-এ পুরো count হয়ে যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা শুরু `i` থেকে প্রতিটা শেষ `j` পর্যন্ত subarray-র যোগফল হিসাব করে `k`-র সাথে মিলিয়ে দেখো।
```text
count = 0
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
if s == k: count += 1
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো nested loop মানে **O(n^2)**। বারবার overlap যোগ হচ্ছে — `i` fix রেখে `j` বাড়ালে যে কাজ, পরের `i`-তে আবার পুনরাবৃত্তি। অথচ prefix sum আর complement-map দিয়ে এক pass-এই সব subarray গোনা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: `sum(i..j) = k` ঘটনাটাকে prefix-এর ভাষায় লেখা যায় — `prefix[j] - prefix[i-1] = k`, অর্থাৎ `prefix[i-1] = prefix[j] - k`। তাই সব জোড়া না দেখে, প্রতিটা j-তে শুধু "আগে কতবার `prefix[j]-k` দেখেছি" জানলেই count হয়ে যায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`seen = {0: 1}` দিয়ে শুরু করো (যাতে শুরু থেকেই `k` হওয়া subarray গোনা যায়)। বাঁ থেকে ডানে হাঁটো; প্রতিটা `x`-এ `running += x`, তারপর `count += seen.get(running - k, 0)` (এই prefix কতবার দরকারি complement-রূপে আগে এসেছে), শেষে `seen[running]` এক বাড়াও। এক pass, O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব subarray-র sum মিলাব" (O(n^2)) ভুলে গিয়ে ভাবো "prefix sum-এর complement (`running − k`) আগে কতবার দেখেছি গুনব।" Two Sum-এর complement trick-ই, শুধু value-র জায়গায় prefix sum।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1, 2, 1], k = 3` দিয়ে (patterns.md-র উদাহরণ):
```text
seen = {0:1}
x=1: running=1; need 1-3=-2 (নেই); seen={0:1, 1:1}
x=2: running=3; need 3-3=0 (আছে 1 বার!) count=1; seen={0:1,1:1,3:1}
x=1: running=4; need 4-3=1 (আছে 1 বার!) count=2; seen={0:1,1:1,3:1,4:1}
answer: 2 -> subarray [1,2] আর [2,1]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[1, 2, 3]`, `k = 3`:
1. `seen={0:1}`, `running=0`, `count=0`।
2. `x=1`: `running=1`; need `1-3=-2` (নেই, +0); `seen={0:1, 1:1}`।
3. `x=2`: `running=3`; need `3-3=0` (আছে 1 বার) → `count=1`; `seen={0:1,1:1,3:1}`।
4. `x=3`: `running=6`; need `6-3=3` (আছে 1 বার) → `count=2`; `seen={...,6:1}`।
5. ফল: `count = 2` (subarray `[1,2]` আর `[3]`)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def subarray_sum(nums, k):
count = 0
running = 0
seen = {0: 1} # prefix sum -> কতবার দেখা গেছে
for x in nums:
running += x
count += seen.get(running - k, 0) # আগে running-k দেখেছি?
seen[running] = seen.get(running, 0) + 1
return count
# ---- tests ----
assert subarray_sum([1, 1, 1], 2) == 2
assert subarray_sum([1, 2, 3], 3) == 2 # [1,2] আর [3]
assert subarray_sum([1, -1, 0], 0) == 3 # negative + 0
assert subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7) == 4
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = {0: 1}` — খালি prefix একবার ধরা; এতে শুরু থেকেই `k` হওয়া subarray গোনা যায়।
- `running += x` — চলমান prefix sum update।
- `count += seen.get(running - k, 0)` — এই point-এ শেষ হওয়া কয়টা subarray-র sum ঠিক `k`; প্রতিটা পুরনো `running-k` prefix একটা subarray।
- `seen[running] = seen.get(running, 0) + 1` — এখনকার prefix-এর frequency বাড়াও (পরের জন্য)।
- lookup-টা insert-এর **আগে** — যাতে দৈর্ঘ্য-0 subarray ভুল করে না গোনা হয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,1,1], k=2` → prefix 0,1,2,3; complement মিলে 2 বার → `2`, assert pass। `[1,2,3], k=3` → `2`; `[1,-1,0], k=0` → `[1,-1]`, `[0]`, `[1,-1,0]` মিলে `3`; `[3,4,7,2,-3,1,4,2], k=7` → `4`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — এক pass; প্রতিটা element-এ একবার O(1) lookup আর একবার O(1) insert।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — সবচেয়ে খারাপ ক্ষেত্রে প্রায় সব prefix sum আলাদা হয়ে dict-এ জমা হতে পারে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `seen = {0: 1}` শুরু না করা — তখন শুরু থেকেই (`prefix == k`) হওয়া subarray গুলো বাদ পড়ে।
- insert আগে করে তারপর lookup — তখন current prefix নিজেকেই complement বানিয়ে দৈর্ঘ্য-0 subarray গোনে; lookup আগে, insert পরে।
- শুধু sorted/positive ভেবে sliding window লাগানো — negative থাকলে window monotonic নয়, তাই prefix + hash map-ই সঠিক।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Two Sum-এর complement lookup (#2) + prefix sums (Static Range Sum #9)। দুটোই "দরকারি জিনিস আগে দেখেছি কিনা" hash map-এ মেলায়। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 3 — Prefix Sums" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Two Sum (complement lookup) —