Prefix Sumprefix sum · range sum · prefix + hash map · 2D prefix
في الفصل اللي فات (Sliding Window) شفت إن الـ window بيقع أول ما يبقى فيه أرقام سالبة، لأن تكبير الـ window ممكن يصغّر المجموع. دلوقتي هنتعلم الأداة اللي بتشتغل في الحالة دي بالظبط: بتجمع الـ array مرة واحدة in one pass، وبعدها مجموع أي subarray يبقى طرحة واحدة. ولو حطيت جنبها hash map، تعدّ الـ subarrays اللي مجموعها k حتى مع السالب.
هتطلع من الفصل ده وإنت عارف
- تبني prefix array طوله
n + 1، وتعرف ليه الخانة الزيادة دي بتشيلifو bugs. - تكتب
prefix[r + 1] - prefix[l]من دماغك، وتشتقها لو نسيتها، من غير off-by-one. - تفهم ليه prefix + hash map بيعدّ الـ subarrays مع السالب، وليه الـ map بتبدأ بـ
{0: 1}، وليه بنسأل قبل ما نسجّل. - تحل 303 و 724 و 238 و 560 و 525 و 974، كل واحدة بتزوّد فكرة واحدة على اللي قبلها.
ليه Prefix Sum؟
خد المسألة دي: array ثابتة، وهتتسأل queries كتير من النوع ده: «مجموع العناصر من l لـ r كام؟». أول حل بييجي في دماغك: loop لكل query.
صح، بس كل query بتاخد O(n). مع n = 100,000 عنصر و q = 100,000 query، ده 10 مليار عملية في الـ worst case، يعني TLE أكيد. بص عليه على 3 queries بس:
المشكلة إننا بنجمع نفس الأرقام تاني وتالت، وبنرمي المجموع كل مرة. الـ key insight: نجمع مرة واحدة من الأول للآخر، ونحفظ المجموع عند كل خطوة. بعدها أي query تبقى طرحة.
النتيجة: build في O(n) مرة واحدة، وكل query في O(1). يعني حوالي 200,000 عملية بدل 10 مليار.
طب إزاي تعرف من كلام المسألة إنها محتاجة prefix sum أصلًا؟
إزاي تعرفه من المسألة
أي مسألة فيها مجموع جزء متصل (subarray، مش subsequence) مرشّحة لـ prefix sum. الكلمات دي بتقولك كده:
لو الـ array بتتعدّل بين الـ queries، كل update محتاج يعيد بناء الـ prefix في O(n)، والحل الصح Fenwick tree أو segment tree. ولو كله موجب والمطلوب أطول أو أقصر window، الـ sliding window أحسن لأنه O(1) memory. ولو subsequence، العناصر مش متصلة أصلًا، والطرح مالوش معنى.
| النوع | الفكرة | بتخزّن إيه | مسائل |
|---|---|---|---|
| مجموع range | prefix[r + 1] - prefix[l] | prefix array طوله n + 1 | 1480، 303، 304 |
| شمال ويمين | اليمين = الكل - الشمال - العنصر | متغيّرين بس | 724 |
| حاصل ضرب | ضرب الشمال × ضرب اليمين | prefix و suffix products | 238 |
| عدّ subarrays بمجموع معيّن | عايز prefix قديم قيمته sum - k | map: قيمة → count | 560، 930، 1248 |
| أطول subarray بشرط | نفس الـ sum اتكرر = اللي بينهم مجموعه 0 | map: قيمة → أول index | 525 |
| باقي القسمة | نفس الباقي = الفرق بيقبل القسمة | count لكل باقي | 974، 523 |
flowchart TD
A["Contiguous subarray + sum?"] --> B{"Array updated between queries?"}
B -- yes --> T["Fenwick / segment tree"]
B -- no --> C{"Many range-sum queries?"}
C -- yes --> P["Prefix array of n + 1, O(1) per query"]
C -- no --> D{"Count or longest with an exact sum, negatives allowed?"}
D -- yes --> H["Prefix sum + hash map"]
D -- no --> E{"All positive, longest or shortest window?"}
E -- yes --> W["Sliding window"]
E -- no --> X["Left / right totals, or prefix x suffix"]
اسأل نفسك الأسئلة دي بالترتيب ده.
عرفت إمتى تستخدمه. نبدأ من الأساس: إزاي تبني الـ prefix، وليه طوله n + 1 مش n؟
بناء الـ prefix array، وليه طوله n + 1
prefix[i] = مجموع أول i عناصر، يعني nums[0] + ... + nums[i - 1]. الـ i هنا عدد عناصر، مش index في nums.
يعني prefix[0] = مجموع ولا حاجة = 0 (الـ empty prefix، زي العداد قبل ما العربية تتحرك)، و prefix[n] = مجموع الـ array كلها. من 0 لـ n دول n + 1 قيمة. والخانة الزيادة دي sentinel: هي اللي هتخلّي صيغة الـ range واحدة لكل الحالات من غير if.
n + 1خانة: واحدة لكل عدد عناصر من 0 لـ n. والـ.fill(0)مهم:new Array(7)لوحدها خاناتهاundefined، فأول سطر في الـ loop هيعملundefined + 2 = NaN، silent bug يبوّظ كل اللي بعده.- ليه
i < nمشi <= n؟ الـiهنا index فيnums، وآخر index فيهاn - 1. لو كتبت<=هتقراnums[n]=undefinedوتكتبNaNفي خانة زيادة. السؤال اللي يحميك: الـ i دي index في أنهي array؟ - الجديد = اللي قبله + عنصر واحد، مش بنجمع من الأول كل مرة، وده اللي بيخلّي الـ build
O(n). وبنكتب فيi + 1لأن الـ prefix "متأخر" عنnumsبخانة. prefix[n]هو مجموع الكل، معلومة هتحتاجها في Find Pivot Index.
الصف التاني هو prefix. لاحظ إن prefix[i] واقف تحت nums[i] في الرسمة، بس معناه مجموع اللي قبل nums[i]:
عندك الـ prefix. طب إزاي تطلّع منه مجموع range معيّن في طرحة واحدة؟
مجموع أي range في O(1)
عايز nums[l] + ... + nums[r] والاتنين داخلين. ما تحفظش الصيغة، اشتقها مرة وإنت فاهم:
يعني prefix[r + 1] فيه اللي عايزه وزيادة من قدّام، والزيادة دي هي أول l عناصر = prefix[l]. اطرحها، يفضل اللي عايزه بالظبط.
lوrindices من 0، والاتنين داخلين. ده الشكل اللي LeetCode بيدّيه غالبًا.- ليه
r + 1؟prefix[r]بيقف عندnums[r - 1]، يعنيnums[r]مش جوّاه. محتاجين أولr + 1عناصر. - ليه
prefix[l]مشprefix[l - 1]؟ اللي بنشيله هو اللي قبلl، وده أولlعناصر بالظبط. ولماl = 0،prefix[0] = 0فمفيش حاجة بتتشال، من غيرif. - طرحة واحدة،
O(1)مهما كان الـ range طويل. الكبير ناقص الصغير، مش العكس.
3 queries: واحدة في النص، وواحدة بتبدأ من 0، وواحدة عنصر واحد. الأحمر هو اللي بنطرحه:
الـ prefix طوله n + 1. عايز مجموع nums[2..5] (الاتنين داخلين). تكتب إيه؟
prefix[5] - prefix[2]prefix[6] - prefix[2]prefix[6] - prefix[1]prefix[5] - prefix[1]
prefix[6] = nums[0..5]، و prefix[2] = nums[0..1]، والفرق = nums[2..5]. الأول ناقصه nums[5]، والتالت فيه nums[1] زيادة.
الصيغة سهلة، لحد ما تقابل حل مكتوب بشكل تاني، أو مسألة بتعدّ من 1. منين بييجي الـ off-by-one بالظبط؟
0-indexed و 1-indexed: منين بييجي الـ off-by-one
هتلاقي الـ prefix sum مكتوب بأكتر من شكل في الحلول، ودي أكبر مصدر للخلبطة:
| الشكل | التعريف | مجموع l..r | الفخ |
|---|---|---|---|
| طول n + 1 (بتاعنا) | prefix[i] = أول i عناصر | prefix[r+1] - prefix[l] | ولا حاجة، صيغة واحدة لكل الحالات. |
| نفس الطول n | pre[i] = nums[0..i] والـ i داخل | pre[r] - pre[l-1] | لما l = 0: pre[-1] = undefined، والنتيجة NaN. |
| المسألة بتعدّ من 1 | "من العنصر رقم L للعنصر رقم R" | prefix[R] - prefix[L-1] | لو استخدمت R + 1 هنا هتزحلق خانة. |
مش غلط، بس لازم تفتكر الـ edge case كل مرة، و JS مش هتنبّهك لو نسيت: pre[-1] بيرجع undefined عادي، و 5 - undefined = NaN. عشان كده الدليل بيستخدم n + 1 دايمًا.
وحتى loop الـ build ليها شكلين صح، والـ < بتتغيّر حسب الـ i ماشية على أنهي array:
l = L - 1 و r = R - 1)، واستخدم نفس prefix[r + 1] - prefix[l]. صيغة واحدة في دماغك أأمن من تلاتة.
تمام في 1D. طب نفس الفكرة تنفع على matrix؟
Prefix Sum في 2D (باختصار)
نفس الفكرة: P[r][c] = مجموع المستطيل من (0, 0) لـ (r - 1, c - 1)، بصف زيادة وعمود زيادة أصفار عشان الحواف. الـ trick كله اسمه inclusion-exclusion: لما تجمع المستطيل اللي فوق واللي على الشمال، الحتة المشتركة بتتجمع مرتين، فتطرحها مرة. هتحتاجه في LeetCode 304، والـ grids عمومًا في Graphs على Grid.
- فخ JS مشهور:
new Array(rows + 1).fill(new Array(cols + 1).fill(0))بيحط نفس الـ array الداخلية في كل الصفوف، فتعديل صف بيعدّل الكل.Array.fromمع function بتعمل array جديدة لكل صف. - بنلف على خانات الـ matrix (
< rowsو< cols)، وبنكتب فيP[r + 1][c + 1]لأن الـ P متأخرة خانة في الاتجاهين. - الخانة + المستطيل اللي فوق + اللي على الشمال، والاتنين فيهم الركن
P[r][c]مرتين، فبنطرحه مرة. - الكبير، ناقص الشريط اللي فوق، ناقص الشريط اللي على الشمال. الركن اتطرح مرتين، فبنرجّعه بـ
+ P[r1][c1]. وكل+ 1جاي من نفس قاعدة الـ 1D.
الشبكة هي P، والصفوف تحتها هي الـ matrix. الأخضر الخانة الجديدة، والـ teal اللي بنجمعه، والأحمر الركن اللي بنطرحه:
التعقيد: الـ build O(rows × cols)، وكل query O(1).
كده الأدوات كلها معاك. نطبّقها على أول مسألة حقيقية فيها queries كتير.
مثال محلول 1: Range Sum Query - Immutable
اعمل class بتاخد array أرقام مرة واحدة في الـ constructor، وبعدها بتجاوب نداءات كتير لـ sumRange(left, right): مجموع العناصر من left لـ right والاتنين داخلين. الـ array مش بتتغيّر، والنداءات ممكن توصل 10⁴.
ده التطبيق المباشر للي فات. الجديد هنا إن الحل class: الـ precompute في الـ constructor مرة واحدة، والـ query في method بتتنادى كتير.
نفكّر فيها مع بعض
- Brute force: loop جوه
sumRange، يعنيO(n)لكل نداء، و 10⁸ في الـ worst case. - الـ key insight: الـ array ثابتة، فـ build مرة في الـ constructor بـ
O(n)، وكل نداء طرحةO(1). - الخطة: نخزّن الـ prefix على الـ object نفسه (
this.prefix) عشانsumRangeيشوفه. - Edge cases:
left = 0، وleft = right، والـ array كلها، وأرقام سالبة.
- LeetCode ساعات بيدّيك القالب القديم:
var NumArray = function(nums) {...}وNumArray.prototype.sumRange = .... نفس الكلام بالظبط، استخدم اللي القالب بيدّيهولك. - ليه
this.prefixمشconst prefix؟ الـconstبيموت لما الـ constructor يخلص، وsumRangeهيضربReferenceError. الـthisبيخزّنه على الـ object. - نفس loop الـ build، وبتشتغل مرة واحدة مهما كان عدد النداءات.
- نفس الصيغة:
right + 1عشانrightداخل، وleftمن غير- 1.
| النداء | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| sumRange(0, 5) | 12 | left = 0: prefix[0] = 0 بيمنع الـ NaN |
| sumRange(4, 4) | -3 | عنصر واحد: الفرق بين خانتين جنب بعض |
| sumRange(1, 3) | 6 | range في النص، والسالب جوّاه |
| nums = [7], sumRange(0, 0) | 7 | عنصر واحد في الـ array: الـ prefix طوله 2 |
التعقيد: الـ constructor O(n) وقت و memory، وكل sumRange O(1). يعني q نداء = O(n + q) بدل O(n × q).
O(n). الحل ساعتها Fenwick أو segment tree بـ O(log n). مش لازم تكتبهم، بس لازم تعرف إن ده حدّ الـ prefix sum.
هنا خزّنّا prefix array كامل. طب لو كل اللي محتاجه لكل index هو مجموع شماله ومجموع يمينه، محتاج array أصلًا؟
مثال محلول 2: Find Pivot Index
دوّر على أول index من الشمال يكون مجموع اللي على شماله بيساوي مجموع اللي على يمينه. العنصر نفسه مش محسوب في أي ناحية، والناحية الفاضية مجموعها 0. لو مفيش، رجّع -1.
الجديد هنا إن مش محتاجين prefix array خالص: الشمال running sum بنحسبه on the fly، واليمين = total - left - nums[i].
نفكّر فيها مع بعض
- Brute force: لكل index، loop للشمال و loop لليمين.
O(n²). - بالـ prefix array: الشمال
prefix[i]واليمينprefix[n] - prefix[i + 1].O(n)بس بـO(n)memory. - الـ key insight: اليمين = الكل - الشمال - العنصر. فلو معانا
totalمرة، وleftSumبيكبر وإحنا ماشيين، يبقىO(1)memory. الـleftSumده هوprefix[i]بالظبط. - Edge cases: الـ pivot عند index 0 أو آخر index، وعنصر واحد (الإجابة 0)، وأرقام سالبة.
- مجموع الكل في one pass، وده
prefix[n]من غير array. لو كتبتها بـreduce، ما تنساش الـ0:reduceعلى array فاضية من غير initial value بيضرب error. leftSum = 0لأن شمال index 0 فاضي. نفسprefix[0] = 0.- ليه
- nums[i]؟ الـ pivot مش في أي ناحية. من غيره هتقارن الشمال باليمين + الـ pivot. - أول تساوي نعمل early return، وبما إننا ماشيين من الشمال، ده الـ leftmost.
- ليه بعد المقارنة؟ الـ invariant وقت المقارنة:
leftSum= مجموعnums[0..i-1]بالظبط. لو ضفت قبل الـif، الـ pivot هيتحسب في الشمال. - لفّينا كله ومفيش تساوي.
الشمال متعلّم seen، واليمين جوه الـ range، والـ i الحالي بالأصفر:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [2, 1, -1] | 0 | الشمال فاضي = 0، واليمين 1 + (-1) = 0 |
| [5] | 0 | عنصر واحد: الناحيتين فاضيين |
| [1, 2, 3] | -1 | مفيش pivot |
| [-1, -1, 0, 1, 1, 0] | 5 | الـ pivot آخر عنصر: اليمين فاضي |
التعقيد: لفّتين، O(n) وقت و O(1) memory.
نفس فكرة الشمال واليمين، بس لو العملية ضرب مش جمع، والقسمة ممنوعة؟
مثال محلول 3: Product of Array Except Self
رجّع array جديدة، كل خانة i فيها حاصل ضرب كل العناصر ما عدا nums[i]. ممنوع القسمة، والمطلوب O(n).
الجديد هنا إن اليمين مش هينفع يتحسب بطرح من الـ total زي 724 (الطرح هنا يبقى قسمة، وممنوعة)، فبنحسبه بـ pass تانية من الآخر: suffix product.
نفكّر فيها مع بعض
- Brute force: لكل
iاضرب كل اللي غيره.O(n²). - ليه مش القسمة؟ غير إنها ممنوعة، بتقع مع الصفر: في
[3, 2, 0, 4]الضرب الكلي 0، و0 / 0 = NaN، والصح إن خانة الصفر إجابتها 24. - الـ key insight: كل حاجة ما عدا
i= (ضرب الشمال) × (ضرب اليمين). الشمال prefix product، واليمين suffix product. - الخطة: pass من الشمال تكتب ضرب الشمال في
answer، و pass من الآخر بمتغيّرrightتضرب فيه. كده الـ memory الزيادةO(1)(الـ output مش بيتحسب).
- طولها
nبالظبط، خانة لكل عنصر، مشn + 1، لأنها الإجابة نفسها. - ليه
left = 1؟ ضرب ولا حاجة = 1، زي ما مجموع ولا حاجة = 0. ده الـ empty prefix بتاع الضرب، ولو بدأت بـ 0 كل الإجابات هتبقى 0. - الترتيب هو الحل كله: نكتب
leftالأول، وبعدين نضرب فيهnums[i]. لو قلبتهم، كل خانة هتاخد العنصر بتاعها معاها. - ليه
i >= 0مشi > 0؟ index 0 لازم ياخد نصيبه من اليمين برضه، وإلاanswer[0]هيفضل 1. والبدايةn - 1لأنه آخر index. *=مش=: الخانة فيها ضرب الشمال، وإحنا عايزين الشمال × اليمين.- نفس فكرة السطر 7:
nums[i]يدخل فيrightبعد ما استخدمناه.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [2, 3, 4, 5] | [60, 40, 30, 24] | الحالة العادية |
| [3, 2, 0, 4] | [0, 0, 24, 0] | صفر واحد: خانته بس مش صفر. القسمة كانت هتقع هنا |
| [0, 2, 0] | [0, 0, 0] | صفرين: كل خانة فيها صفر من الناحية التانية |
| [-1, 0, 2] | [0, -2, 0] | JS بيطلّع -0 في الآخر (-1 × 0)، بس -0 === 0 و JSON.stringify بيكتبه 0، فالـ judge بيقبله |
التعقيد: لفّتين، O(n) وقت و O(1) memory زيادة.
leftProd و rightProd و answer) لأنها أوضح، وقول إنها O(n) memory، وبعدين optimize للنسخة دي. الـ interviewer عايز يشوفك بتوصل للتحسين.
لحد هنا كل مسألة بتسأل عن range أو index معيّن. طب لو المطلوب تعدّ كل الـ subarrays اللي مجموعها k، والأرقام فيها سالب؟
Prefix Sum + Hash Map: عدّ الـ subarrays
ده المكان اللي الـ sliding window وقع فيه. خد [3, -3, 3] و k = 3: الإجابة 3 ([3] الأولى، و [3, -3, 3]، و [3] التالتة). الـ window بيمسك بداية واحدة لكل نهاية، فبيطلّع 2. مع السالب، أكتر من بداية ممكن تنفع لنفس النهاية، والتصغير مالوش قاعدة.
الـ key insight: كل subarray = فرق بين اتنين prefix
يعني لكل نهاية، السؤال بقى: كام prefix قبلها قيمته prefix[j] - k؟ وده نفس سؤال Two Sum: "شفت الـ complement قبل كده؟"، بس بفرق بدل مجموع، وبـ count بدل وجود. شوف النسخة البطيئة اللي بتجرّب كل زوج prefixes:
الـ loop الداخلية بتسأل سؤال واحد بس: "كام prefix[i] قيمته كذا؟". ده بالظبط اللي الـ hash map بتجاوبه في O(1)، لو خزّنّا فيها كل قيمة prefix شفناها وعدد مراتها.
ليه الـ map بتبدأ بـ {0: 1}؟
في النسخة البطيئة، prefix[0] = 0 كان في الـ array، وهو اللي بيمثّل البدايات من index 0. الـ map بتبدأ فاضية، فلازم نحطه بإيدنا. من غيره، [3] مع k = 3 هتطلع 0 بدل 1. نفس فكرة الـ n + 1 بشكل map.
وليه count مش Set؟
لأن القيمة بتتكرر، وكل تكرار بداية مختلفة. في الـ animation، القيمة 2 ظهرت في prefix[3] و prefix[5]، فلما prefix[6] = 5 سأل عن 2 لقى اتنين، يعني 2 subarrays. الـ Set كانت هتعدّ واحد.
الـ loop الداخلية دي هي اللي هنشيلها بـ map. إزاي الكود بيبقى one pass؟
مثال محلول 4: Subarray Sum Equals K
عدّ كل الـ subarrays المتصلة (فيها عنصر واحد على الأقل) اللي مجموعها k بالظبط. الأرقام ممكن تبقى سالبة أو صفر.
الجديد هنا إن الـ map بتجاوب "كام prefix قديم قيمته sum - k؟" في O(1)، بدل الـ loop الداخلية.
نفكّر فيها مع بعض
- Brute force: لكل بداية، مجموع جاري لحد الآخر.
O(n²)وقت وO(1)memory. قوله كبداية. - ليه مش sliding window؟ السالب: تكبير الـ window ممكن يصغّر المجموع، وأكتر من بداية تنفع.
- الخطة:
sumجاري، ولكل عنصر:count += seen.get(sum - k)، وبعدين سجّلsum. - Edge cases: subarray من index 0 (محتاج
{0: 1})، وk = 0(محتاج نسأل قبل ما نسجّل)، وأصفار كتير (محتاجين count).
- الـ map: قيمة prefix ← count. الـ
0مرة واحدة هو الـ empty prefix، ومن غيره البدايات من index 0 ما تتعدّش. والـ Map أنضف من object: المفاتيح بتفضل أرقام، ومفيش prototype keys. sumهو الـ running prefix، بيبدأ 0 لنفس السبب.- بعد السطر ده
sum=prefix[j]للنهاية الحالية. sum - kمشk - sum: من الجبرprefix[i] = prefix[j] - k. لو شكّيت، جرّب[3]وk = 3: الـneedلازم يطلع 0.- الـ
|| 0عشانgetبيرجّعundefinedلو مش موجود، وcount += undefined=NaNللأبد. و+=مش++: لوneedاتشافت 3 مرات، دول 3 بدايات مختلفة. - ليه بعد العدّ؟ الـ invariant: الـ map فيها الـ prefixes اللي قبل النهاية الحالية بس. لو سجّلت الأول ومع
k = 0، هتلاقي نفسك وتعدّ subarray فاضي:[1, 2, 3]هتطلع 3 بدل 0.
الأخضر في الـ map هو الـ need اللي لقيناه، والأصفر الـ sum اللي بنسجّله:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [3], k = 3 | 1 | من غير {0: 1} هتطلع 0 |
| [1, 2, 3], k = 0 | 0 | لو سجّلت قبل ما تعدّ هتطلع 3 |
| [0, 0, 0], k = 0 | 6 | القيمة 0 بتتكرر، والـ count بيكبر |
| [1, -1, 1, -1], k = 0 | 4 | بـ Set بدل count هتطلع 3 |
| [3, -3, 3], k = 3 | 3 | الـ sliding window هنا بيطلّع 2 |
التعقيد: one pass، وكل عملية على الـ Map O(1) average، يعني O(n) وقت، و O(n) memory للـ map.
{0: 1}؟". جاوب الأول بـ [3, -3, 3]، والتاني بـ [3] و k = 3. مثال صغير بيقنع أكتر من أي كلام.
هنا الـ map كانت بتعدّ. طب لو المطلوب أطول subarray مش عددهم؟
مثال محلول 5: Contiguous Array
array فيها 0 و 1 بس. رجّع طول أطول subarray متصل فيه عدد الأصفار بيساوي عدد الوحايد، أو 0 لو مفيش.
الجديد هنا إن المطلوب أطول مش عدد، فالـ map بتخزّن أول index لكل sum بدل count، وتبدأ {0: -1} بدل {0: 1}. وعشان نوصل لـ "مجموع = 0" بنعمل transform صغير: الـ 0 يبقى -1.
نفكّر فيها مع بعض
- Brute force: لكل بداية، عدّ الأصفار والوحايد وسجّل أطول تساوي.
O(n²). - الـ transform: لو الـ 0 بقى -1، "عدد الأصفار = عدد الوحايد" معناها "المجموع = 0"، لأن كل 1 بيلغي -1.
- إمتى مجموع = 0؟ لما نفس الـ sum يتكرر: الجزء اللي بين المرتين مجموعه صفر.
- أطول: عايزين البداية أبعد حاجة لورا، يعني أول ظهور للـ sum، ومش بنحدّثه أبدًا.
- Edge cases: الـ array كلها متوازنة (محتاجة الـ -1)، مفيش جزء متوازن (0)، و sum بيتكرر كذا مرة.
- الـ map: sum ← أول index. الـ
-1معناها إن الـ sum كان 0 قبل أول عنصر، فلو الجزء المتوازن بيبدأ من 0 ويخلص عندi، طولهi - (-1) = i + 1من غير edge case. - loop بـ index مش
for...of، لأننا محتاجين الـ index نحسب بيه الطول. - الـ transform on the fly، من غير ما نعدّل الـ array نفسها.
- ليه
i - jمشi - j + 1؟ الجزء بيبدأ منj + 1، لأنjآخر عنصر قبله. جرّب:j = -1وi = 1يدّي 2، صح. - ليه الـ
setفي الـ else بس؟ لو حدّثت كل مرة، هتقيس من بداية أقرب فالطول يقصر:[0, 1, 0, 1]هتطلع 2 بدل 4.
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [0, 1] | 2 | الـ array كلها: محتاجة {0: -1} |
| [0, 0, 0] | 0 | مفيش جزء متوازن |
| [0, 1, 0, 1] | 4 | لو حدّثت أول index هتطلع 2 |
| [1, 0, 1, 1, 0, 0] | 6 | الـ sum بيرجع للصفر في الآخر بس |
التعقيد: O(n) وقت و memory. ولو عايز تستغنى عن الـ Map: الـ sum دايمًا بين -n و n، فـ array طولها 2n + 1 مع offset n تنفع، وأسرع شوية.
{0: 1}. "أطول" ← map فيها أول index وتبدأ {0: -1}. ولو "أطول subarray مجموعه k"، نفس الكود ده بس اسأل عن sum - k.
لحد دلوقتي بندوّر على مجموع بالظبط. طب لو الشرط إن المجموع يقبل القسمة على k؟
مثال محلول 6: Subarray Sums Divisible by K
عدّ الـ subarrays المتصلة (غير الفاضية) اللي مجموعها بيقبل القسمة على k. الأرقام ممكن تبقى سالبة، و k موجب.
الجديد هنا إن الـ key في الـ map بقى الباقي مش الـ sum، وده بيجيب معاه فخ الـ % السالب في JS.
نفكّر فيها مع بعض
- Brute force: كل subarray ومجموعه الجاري،
O(n²). - الـ key insight:
prefix[j] - prefix[i]بيقبل القسمة علىk⟺ الاتنين ليهم نفس الباقي. مثال: 17 و 2 باقيهم 2 على 5، والفرق 15. - الخطة: نفس قالب 560 بالظبط، بس نعدّ prefixes بنفس الباقي. والبواقي من 0 لـ
k - 1، فـ array طولهاkتكفي، وcount[0] = 1هو الـ empty prefix. - الفخ: في JS
-3 % 5 = -3مش 2، مع إن الاتنين نفس الباقي. لازم normalize.
- بعد الـ normalize البواقي من 0 لـ
k - 1، فـ array طولهاkكفاية وأسرع من Map، والـ index هو الباقي. - نفس
{0: 1}: من غيره[5]معk = 5مش هتتعد. - الـ
sumفي حدود المسألة أقصاه حوالي3 × 10⁸، بعيد جدًا عن2⁵³. - أهم سطر. الـ
%في JS بياخد إشارةsum، فـcount[-3]=undefinedوالنتيجةNaN. أول%بيجيبه بين-(k-1)وk-1، والـ+ kبيخليه موجب، وتاني%بيرجّعه تحتk. - كل prefix قديم بنفس الباقي = subarray مجموعه بيقبل القسمة، زي
seen.get(need)في 560. - نسجّل بعد العدّ، لنفس سبب 560.
الصف التاني count، والـ index فوق كل خانة هو الباقي. ركّز على الـ sum السالب:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [4, -7, 2, 5, -3], k = 5 | 3 | بالـ % الخام (مع Map) هتطلع 1 |
| [5], k = 5 | 1 | محتاجة count[0] = 1 |
| [0, 0], k = 3 | 3 | كل subarray مجموعه 0، والـ 0 بيقبل القسمة |
| [1, 2], k = 7 | 0 | مفيش ولا واحد |
التعقيد: O(n) وقت و O(k) memory.
كده الأفكار كلها خلصت. إيه الغلطات اللي بتوقّع الناس في كل اللي فات؟
غلطات مشهورة
كلها بتطلّع Wrong Answer أو NaN من غير أي error، وده اللي بيخلّيها صعبة تتلاقي.
1. prefix طوله n، و l = 0 بيطلّع NaN
الحل: prefix طوله n + 1 و prefix[r + 1] - prefix[l]. أأمن من إنك تفتكر (l > 0 ? pre[l - 1] : 0) كل مرة.
2. نسيت {0: 1}
الحل: new Map([[0, 1]]). ونفس الفكرة بشكلين تانيين: {0: -1} في "أطول"، و count[0] = 1 في البواقي.
3. سجّلت الـ sum قبل ما تعدّ
الحل: اسأل الأول، وبعدين سجّل. الـ map لازم يبقى فيها اللي قبل العنصر الحالي بس.
4. Set بدل count
الحل: Map فيها count، و count += seen.get(need) || 0.
5. الـ % السالب في JS
الحل: ((sum % k) + k) % k. هتقابلها في أي مسألة فيها باقي وأرقام سالبة. (C++ و Java نفس المشكلة، و Python بترجّع موجب لوحدها.)
6. حدّثت أول index في مسائل "أطول"
الحل: set جوه else بس. "أطول" = أبعد بداية = أول ظهور.
عارف الغلطات. تقدر تتجنبها وإنت بتجاوب؟
اختبر نفسك
في Subarray Sum Equals K، ليه الـ map بتبدأ بـ {0: 1}؟
- عشان الـ map ما تبقاش فاضية وتضرب error
- عشان الـ 0 هو الـ empty prefix، ومن غيره الـ subarrays اللي بتبدأ من index 0 مش هتتعد
- عشان k ممكن يبقى 0
- مش ضروري، الحل بيشتغل من غيره
subarray بيبدأ من 0 مجموعه prefix[j+1] - prefix[0]، فمحتاج prefix[0] = 0 يبقى في الـ map. وموضوع k = 0 بيتحل بترتيب السطور، مش بالـ {0: 1}.
في JS، -7 % 3 بيساوي كام؟ وبعد ((-7 % 3) + 3) % 3؟
2و2-1و2-1و-11و1
JS بتاخد إشارة الرقم اللي بيتقسم: -7 = 3 × (-2) + (-1). والـ normalize: (-1 + 3) % 3 = 2، وده الصح رياضيًا: -7 = 3 × (-3) + 2.
مسألة فيها نوعين من العمليات بالتبادل: "غيّر nums[i]" و "مجموع l..r كام؟". الـ prefix sum العادي ينفع؟
- أيوه، كل حاجة
O(1) - أيوه، بس الـ query تبقى
O(log n) - مش كويس: كل update بيعدّل كل الـ prefix اللي بعده،
O(n). الحل Fenwick أو segment tree - لأ، لازم brute force
لو غيّرت nums[2]، كل prefix[3..n] لازم تتغيّر. الـ prefix sum بيلمع لما الـ array immutable، زي ما اسم 303 بيقول.
في Contiguous Array، ليه بنخزّن أول index لكل sum وما بنحدّثهوش؟
- عشان الـ Map ما تكبرش
- عشان أول ظهور = أبعد بداية = أطول subarray
- عشان الـ index الأخير ممكن يبقى -1
- مش فارقة، الاتنين هيدّوا نفس الإجابة
الطول i - j، فكل ما j يصغر، الطول يكبر. لو حدّثت، [0, 1, 0, 1] هتطلع 2 بدل 4.
array فيها سالب، والمطلوب طول أطول subarray مجموعه k. أحسن أداة؟
- Sliding window
- Prefix + map فيها count، وتبدأ
{0: 1} - Prefix + map فيها أول index، وتبدأ
{0: -1}، وتسأل عنsum - k - Sort وبعدين two pointers
السالب بيقفل الـ window. و"أطول" يعني أول index زي 525، بس بتسأل عن sum - k. والـ sort بيبوّظ الـ "متصل".
تمرين: فكّر قبل ما تفتح
عدّ الـ subarrays المتصلة اللي فيها بالظبط k أرقام فردية.
تلميح 1
الأرقام نفسها مش مهمة، المهم فردي ولا زوجي. اعمل transform: الفردي 1 والزوجي 0، زي ما عملنا في Contiguous Array.
تلميح 2
بعد الـ transform، عدد الفرديات في أي subarray = مجموعه. يعني دي Subarray Sum Equals K بالحرف: نفس الـ map، ونفس {0: 1}، ونفس الترتيب.
الحل
x % 2 === 1 شغالة هنا لأن الأرقام موجبة. لو ممكن تبقى سالبة، -3 % 2 = -1 (نفس فخ الـ modulo)، فاكتب x % 2 !== 0.
لو جاوبت كله صح، إنت جاهز. تتمرن على أنهي مسائل، وبأنهي ترتيب؟
اتمرن على LeetCode بالترتيب
حلها بالترتيب ده، كل مسألة بتزوّد فكرة واحدة. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للقالب بتاعها هنا، وبعدين حاول تاني من غير ما تبص.
- Running Sum of 1d Arrayالـ build وبس. سخّن إيدك على الـ loop وحدودها.
- Range Sum Query - Immutableالمثال 1:
n + 1وprefix[r + 1] - prefix[l]من دماغك. - Range Sum Query 2D - Immutableنفس الفكرة في 2D: inclusion-exclusion.
- Matrix Block Sum2D prefix مع حدود لازم تقصّها جوه الـ matrix بـ
Math.maxوMath.min. - Find Pivot Indexالشمال واليمين من غير array.
- Product of Array Except Selfنفس الشمال واليمين بالضرب، و pass من الآخر.
- Subarray Sum Equals Kأهم قالب في الفصل: map بـ count و
{0: 1}. - Binary Subarrays With Sumنفس القالب على 0 و 1. اكتبه في دقايق.
- Count Number of Nice Subarraysالتمرين اللي فوق: transform الأول، وبعدين القالب.
- Contiguous Array"أطول" يعني أول index و
{0: -1}. - Subarray Sums Divisible by Kالـ key بقى الباقي، وصلّح الـ
%السالب. - Continuous Subarray Sumباقي + أول index + طول 2 على الأقل: 525 و 974 مع بعض.
- Path Sum IIIاختياري بعد فصل Binary Trees: نفس قالب 560 على مسارات في tree.
عايز الفصل كله في صفحة واحدة تراجع منها قبل الانترفيو؟
الخلاصة
| السؤال | الإجابة |
|---|---|
| طول الـ prefix؟ | n + 1، و prefix[0] = 0. |
مجموع l..r؟ | prefix[r + 1] - prefix[l]. لو المسألة بتعدّ من 1، حوّل لـ 0 الأول. |
| الـ map بتبدأ بإيه؟ | {0: 1} للعدّ، {0: -1} للأطول، count[0] = 1 للبواقي. |
| أسأل ولا أسجّل الأول؟ | اسأل الأول، وإلا هتعدّ subarray فاضي. |
| count ولا أول index؟ | "كام" ← count. "أطول" ← أول index وما تحدّثوش. |
| الباقي السالب؟ | ((x % k) + k) % k. |
| Sliding window ولا prefix؟ | كله موجب وعايز أطول أو أقصر: window. فيه سالب أو عايز مجموع بالظبط: prefix + map. |
| Complexity؟ | O(n) وقت، O(n) memory، و O(1) لكل query. |
الفصل الجاي: Sorting و Intervals. هناك الـ prefix sum متخبّي في مسائل الـ intervals: كل meeting بتبدأ تحط +1 وكل واحدة بتخلص تحط -1، وبعد ما ترتّب الأحداث بالوقت، الـ running sum هو عدد الـ meetings الشغالة في أي لحظة. ده اسمه sweep line، وأساسه الجمع الجاري اللي اتعلمته هنا. بس الأول لازم تعرف الـ sort بيشتغل إزاي، وده أول حاجة هناك.