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