Running Sum of an Array
لديك مصفوفة من الأعداد الصحيحة nums. أعد مصفوفة جديدة بالطول نفسه، يكون عنصرها عند الفهرس i هو nums[0] + nums[1] + ... + nums[i]، أي المجموع التراكمي بعد قراءة أول i+1 أعداد من اليسار.
الدالة
- numsinteger-array
- الأعداد المراد جمعها من اليسار إلى اليمين
- تُرجعinteger-array
- المجاميع التراكمية، واحد لكل عنصر من عناصر nums
القيود
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- كل مجموع تراكمي يلائم عددًا صحيحًا موقّعًا من 32 بت.
أمثلة
- المدخلات
- nums = [3, 1, 4, 1, 5]
- المخرجات
- [3, 4, 8, 9, 14]
- الشرح
- واصل الإضافة:
3، ثم3 + 1 = 4، و4 + 4 = 8، و8 + 1 = 9، و9 + 5 = 14. يُضاف كل مجموع إلى فهرس العدد الذي أُضيف أخيرًا.
- المدخلات
- nums = [-2, 5, -3]
- المخرجات
- [-2, 3, 0]
- الشرح
- الأعداد السالبة تُنقص المجموع:
-2، ثم-2 + 5 = 3، ثم3 + (-3) = 0.
- المدخلات
- nums = [7]
- المخرجات
- [7]
- الشرح
- للعدد المفرد مجموع جارٍ واحد، وهو العدد نفسه، لذا فالإجابة هي
[7].
+13 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك إنشاء الشيء نفسه لشبكة، بحيث تحتوي كل خلية على مجموع المستطيل الممتد من الزاوية العلوية اليسرى إلى تلك الخلية؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
كيف ترتبط الإجابة عند الفهرس
iبالإجابة عند الفهرسi-1؟يختلف المجموعان بمقدار عدد واحد بالضبط، وهو
nums[i]. لن تحتاج أبدًا إلى جمع بادئة من البداية مرة أخرى.احتفِظ بمتغير واحد هو
total. مرّ علىnumsمن اليسار إلى اليمين، وأضف كل عدد إلىtotal، واكتبtotalفي الإجابة عند الفهرس نفسه.
الحل
كل إجابة هي مجموع بادئة من nums، وتختلف كل بادئتين متجاورتين بعنصر واحد بالضبط. إن إعادة حساب كل بادئة من البداية تكرر معظم العمل، بينما يتيح الاحتفاظ بمجموع واحد وتحديثه الحصول على كل إجابة بعملية جمع واحدة. والنتيجة هي مصفوفة المجاميع البادئة، الأداة التي تتيح حساب مجاميع النطاقات بسرعة.
اجمع كل بادئة من الصفر
الفكرة
اتبع التعريف حرفيًا. لكل فهرس i، ابدأ بمجموع جديد قيمته 0، وأضف nums[0] حتى nums[i]، ثم خزّن الناتج. بالنسبة إلى [3, 1, 4, 1, 5]، يجمع الناتج الأخير الأعداد الخمسة كلها: 3 + 1 + 4 + 1 + 5 = 14.
هذا صحيح، لكنه يكرر العمل. يبدأ مجموع الفهرس 4 من جديد من nums[0]، رغم أن مجموع الفهرس 3، 9، يحتوي بالفعل على مجموع الأعداد الأربعة الأولى. يتطلب الفهرس i إجراء i+1 عملية جمع، لذا يتطلب المصفوفة كلها 1 + 2 + ... + n = n(n+1)/2. عندما يكون n = 5000، فهذا يعادل نحو 1.25 × 10^7 عملية جمع، بينما تكفي 5000 عملية.
باستثناء مصفوفة الإجابات، التي تعيدها على أي حال، لا يحتفظ إلا بمجموع وفهرسين، لذا فإن المساحة الإضافية هي O(1).
الخوارزمية
- أنشئ مصفوفة للإجابة بطول
n. - لكل فهرس
i، عيّنtotal = 0. - أضف
nums[j]إلىtotalلكلjمن0إلىi. - خزّن
totalعند الفهرسiفي مصفوفة الإجابة، وأعِد الإجابة بعد الفهرس الأخير.
def runningSum(nums):
result = []
for i in range(len(nums)):
total = 0
for j in range(i + 1):
total += nums[j]
result.append(total)
return resultاحتفظ بمجموع جارٍ
الفكرة
مجموع أول i+1 عددًا هو مجموع أول i عددًا زائدًا على nums[i]: result[i] = result[i-1] + nums[i]. لذلك لا تحتاج أبدًا إلى الرجوع أكثر من خطوة واحدة. احتفظ بمتغير واحد هو total، وأضف إليه كل عدد عند قراءته، ثم اكتب القيمة الجديدة في الإجابة.
بالنسبة إلى [3, 1, 4, 1, 5]، تصبح قيمة total 3، ثم 4، ثم 8، ثم 9، ثم 14، وهذه القيم الخمس هي الإجابة. يُقرأ كل عنصر مرة واحدة ويتطلب عملية جمع واحدة، لذا فالزمن هو O(n). وباستثناء مصفوفة الإجابة، لا تُستخدم سوى الذاكرة اللازمة لـ total، لذا فالمساحة الإضافية هي O(1).
لا يمكن أن يتجاوز حجم أي مجموع هنا 5000 × 10^4 = 5 × 10^7، وهذا يناسب عددًا صحيحًا من 32 بت. مع المدخلات الأكبر، تُعد مجاميع البادئات موضعًا شائعًا لحدوث تجاوز السعة، ويكون استخدام مجموع من 64 بت خيارًا آمنًا افتراضيًا.
الخوارزمية
- أنشئ مصفوفة للإجابة بطول
nواضبطtotal = 0. - مرّ على الفهارس من اليسار إلى اليمين وأضف
nums[i]إلىtotal. - اكتب
totalفي الفهرسiمن مصفوفة الإجابة. - أعِد مصفوفة الإجابة.
def runningSum(nums):
result = []
total = 0
for num in nums:
total += num
result.append(total)
return result
أخطاء شائعة وحالات حدّية
تحتوي الحلقة على سطر واحد ينفّذ العمل الفعلي، لذا تتعلق الأخطاء بمكان تخزين المجموع والوجهة التي ينتقل إليها.
- إعادة ضبط
totalداخل الحلقة. تصبح كل إجابةnums[i]وحدها، وتعود[3, 1, 4]دون تغيير. - استخدام
result[i] = result[i-1] + nums[i]من دون معالجةi = 0. يكون الفهرس-1خارج الحدود في معظم اللغات، أما في Python فهو العنصر الأخير، لذا فإن النسخة التي تعدّل القائمة في مكانها وتبدأ من 0 تضيف العدد الأخير إلى الأول. - إيقاف الحلقة الداخلية في الطريقة الأولى عند
j < i. فهذا يستثنيnums[i]، لذا ينقص كل إجابة عدد واحد. - زيادة طول الإجابة عن طريق النسخ. في R، يؤدي
result <- c(result, total)إلى نسخ المتجه كاملًا في كل خطوة، ما يجعل الطريقة السريعة تربيعية مجددًا. خصّص الحجم الكامل أولًا. - نسيان
*returnSize = numsSizeفي C. من دونه، لن يعرف المستدعي عدد المجاميع التي عليه قراءتها.
أسئلة شائعة4
ما هو المجموع التراكمي لمصفوفة؟
إنها مصفوفة ثانية يكون كل عنصر فيها مجموع كل العناصر حتى الموضع نفسه في المصفوفة الأولى، بما في ذلك العنصر عند ذلك الموضع. وتُسمّى أيضًا المجموع البادئ أو المجموع التراكمي. المجموع التراكمي لـ [3, 1, 4, 1, 5] هو [3, 4, 8, 9, 14].
ما التعقيد الزمني لحساب مجموع تراكمي؟
باستخدام مجموع كلي يُحمل من اليسار إلى اليمين، يكون الزمن O(n)، مع عملية جمع واحدة لكل عنصر، وتكون المساحة الإضافية O(1)، باستثناء مساحة الإجابة. أما إعادة حساب كل مجموع بادئة من البداية فتتطلب n(n+1)/2 عملية جمع، أي O(n²).
هل يمكنك حساب المجموع التراكمي في مكانه؟
نعم. انتقل من الفهرس 1 إلى النهاية واضبط nums[i] += nums[i-1]. عندها يحمل كل عنصر مجموع بادئته، لأن nums[i-1] تحوّل بالفعل إلى مجموع كل ما يسبقه. لا يستخدم هذا أي مصفوفة سوى مصفوفة الإدخال، لكنه يتلف القيم الأصلية.
كيف تساعد المجاميع البادئة في استعلامات مجموع النطاق؟
بمجرد أن تحسب المجاميع التراكمية، يكون مجموع أي مقطع nums[l..r] هو prefix[r] - prefix[l-1]، أو prefix[r] عندما l = 0. باستخدام المجاميع التراكمية [3, 4, 8, 9, 14]، يكون مجموع الفهارس من 2 إلى 4 هو 14 - 4 = 10. يستغرق كل استعلام O(1) من الوقت بعد مرور واحد بتعقيد O(n).
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def runningSum(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [3, 1, 4, 1, 5]
المتوقع
[3, 4, 8, 9, 14]