Minimum Size Subarray Sum
يُعطى لك عدد صحيح موجب target ومصفوفة nums من الأعداد الصحيحة الموجبة. أوجد أقصر مصفوفة فرعية (مجموعة متجاورة من العناصر) يكون مجموعها أكبر من أو يساوي target، وأعِد طولها. إذا لم تصل أي مصفوفة فرعية إلى target، فأعِد 0.
الدالة
- targetinteger
- المجموع الذي يجب أن يبلغه المصفوفة الفرعية أو يتجاوزه
- numsinteger-array
- مصفوفة الأعداد الصحيحة الموجبة
- تُرجعinteger
- طول أقصر مصفوفة فرعية مجموعها لا يقل عن target، أو 0 إذا لم توجد أيٌّ منها
القيود
1 ≤ target ≤ 1091 ≤ nums.length ≤ 2 × 1041 ≤ nums[i] ≤ 104
أمثلة
- المدخلات
- target = 15nums = [4, 2, 9, 3, 7, 1, 5]
- المخرجات
- 3
- الشرح
- لا يصل أي جارين إلى 15: أكبر زوج هو 9 + 3 = 12. أما ثلاثة فتصل: 4 + 2 + 9 = 15 و9 + 3 + 7 = 19، لذا فالإجابة هي 3.
- المدخلات
- target = 11nums = [1, 2, 3, 4]
- المخرجات
- 0
- الشرح
- مجموع المصفوفة بأكملها يساوي 10، وهو أقل من 11، لذا لا تصل أي مصفوفة فرعية إلى الهدف، والإجابة هي 0.
- المدخلات
- target = 8nums = [3, 8, 2]
- المخرجات
- 1
- الشرح
- تصل القيمة 8 إلى الهدف بمفردها، ولا توجد مصفوفة فرعية أقصر من عنصر واحد.
+16 اختبارات مخفية عند الإرسال
سؤال إضافي
كيف ستحلّها إذا كان بإمكان nums أن يحتوي أيضًا على أصفار وأعداد سالبة، بحيث لا تعود النافذة المنزلقة صالحة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
جميع القيم موجبة. ماذا يحدث لمجموع المصفوفة الفرعية عندما تضيف عنصرًا آخر من اليمين، وعندما تزيل عنصرًا من اليسار؟
احتفِظ بنافذة
nums[left..right]ومجموعها. وسّعها من اليمين حتى يصل المجموع إلىtarget. عندئذٍ تكون النافذة مرشّحًا، ويمكنك محاولة تقصيرها.ما دام المجموع أكبر من أو يساوي
target، سجّل طول النافذة وأزِلnums[left]. تتحرك الحافتان إلى اليمين فقط، لذا يدخل كل عنصر النافذة ويغادرها مرة واحدة.
الحل
جميع القيم موجبة، لذا فإن تمديد مصفوفة فرعية يزيد مجموعها دائمًا، وتقليصها يخفضه دائمًا. هذه الحقيقة وحدها تدعم كلا الحلين السريعين. تصبح المجاميع البادئة قائمة مرتبة، لذا يحدد البحث الثنائي الموضع الذي يصل عنده المجموع إلى target لأول مرة. والأفضل من ذلك، أن النهاية المثلى لا تتحرك إلى اليسار عندما تتحرك البداية إلى اليمين، لذا تعثر نافذة واحدة تكبر من اليمين وتتقلص من اليسار على الإجابة في مرور واحد.
امتدّ من كل نقطة بداية
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ثبّت فهرس بداية وأضف القيم واحدة تلو الأخرى باتجاه اليمين. في المرة الأولى التي يصل فيها المجموع الجاري إلى target، يكون لديك أقصر مقطع فرعي يبدأ من ذلك الموضع: فكل مقطع أقصر منه توقف قبل ذلك، وكان مجموعه لا يزال أصغر من المطلوب. لذا سجّل طوله، وتوقف عن التوسيع، وانتقل إلى موضع البداية التالي. الإجابة هي أصغر طول بين جميع مواضع البداية.
عندما تكون target = 15 و[4, 2, 9, 3, 7, 1, 5]، تكون المجاميع عند البدء من الموضع 0 هي 4 و6 و15، ويتوقف الفحص عند طول 3. وعند البدء من الموضع 1، تكون المجاميع 2 و11 و14 و21، ويتوقف عند طول 4. وعند البدء من الموضع 2، تكون المجاميع 9 و12 و19، أي بطول 3 مجددًا. لا يحقق أي موضع بداية نتيجة أفضل من 3.
تظهر المشكلة عندما يصعب الوصول إلى الهدف. إذا لم يصل إليه أي مقطع فرعي، فسيمتد الفحص من كل موضع بداية حتى نهاية المصفوفة: n(n+1)/2 عملية جمع، أي 2 × 10^8 عندما تكون n = 2 × 10^4. كما يعيد كل موضع بداية حساب مجاميع سبق لموضع البداية السابق حسابها.
الخوارزمية
- عيّن
bestإلى 0، ما يعني أنه لم يتم العثور على شيء بعد. - لكل فهرس بداية، عيّن المجموع الجاري إلى 0.
- حرّك فهرس النهاية إلى اليمين انطلاقًا من البداية، مع إضافة
nums[end]إلى المجموع. - عندما يصل المجموع إلى
target، احتفظ بـend-start+1إذا كانت أكبر منbest، وتوقف عن توسيع هذه البداية. - أعِد
best.
def minSubArrayLen(target, nums):
n = len(nums)
best = 0 # 0 means no subarray found yet
for start in range(n):
total = 0
for end in range(start, n):
total += nums[end]
if total >= target:
# The shortest subarray from this start ends here
if best == 0 or end - start + 1 < best:
best = end - start + 1
break
return bestالمجاميع البادئة والبحث الثنائي
الفكرة
لتكن prefix[k] مجموع أول k من القيم، حيث prefix[0] = 0. عندئذٍ يكون مجموع nums[start..end-1] هو prefix[end] - prefix[start]. عند تثبيت البداية، تريد أصغر end بحيث prefix[end] ≥ prefix[start] + target.
كل القيم موجبة، لذا فإن prefix متزايدة بصرامة، ويمكن العثور على أول موضع تصل فيه إلى قيمة ما بالبحث الثنائي. بالنسبة إلى [4, 2, 9, 3, 7, 1, 5]، تكون prefix هي [0, 4, 6, 15, 18, 25, 26, 31]. من موضع البداية 2 تحتاج إلى 6 + 15 = 21؛ وأول قيمة في prefix لا تقل عن 21 هي 25 عند الفهرس 5، لذا فإن النافذة هي nums[2..4] = 9, 3, 7، وطولها 3.
إذا كانت حتى prefix[n] أقل من القيمة التي تحتاج إليها نقطة بداية ما، فلا توجد أي نهاية مناسبة لها، ولن توجد نهاية مناسبة لأي نقطة بداية لاحقة أيضًا، لأن prefix[start] لا يتناقص. توقّف عندها. يتطلب ذلك n عملية بحث ثنائي، بزمن O(n log n)، بالإضافة إلى O(n) لمصفوفة المجاميع التراكمية. أكبر قيمة تتم مقارنتها هي 2 × 10^8 + 10^9، وهي تتسع في عدد صحيح ذي 32 بت.
الخوارزمية
- أنشئ
prefixبطولn+1، بحيث يكونprefix[k+1] = prefix[k] + nums[k]. - لكل موضع بداية، احسب
need = prefix[start] + target. - إذا كان
prefix[n] < need، فتوقّف: لا يمكن لأي موضع بداية لاحق أن ينجح. - ابحث ثنائيًا في المواضع من
start+1إلىnعن أولendبحيثprefix[end] ≥ need، واحتفظ بالقيمةend-startإذا كانت الأقصر حتى الآن. - أعِد أقصر طول، أو 0 إذا لم ينجح أي موضع بداية.
from bisect import bisect_left
def minSubArrayLen(target, nums):
n = len(nums)
# prefix[k] is the sum of the first k values; it only grows
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
best = 0
for start in range(n):
need = prefix[start] + target
if prefix[n] < need:
break # no window from here on can reach target
# The first end with prefix[end] >= need closes the shortest window
end = bisect_left(prefix, need, start + 1)
if best == 0 or end - start < best:
best = end - start
return bestالنافذة المنزلقة
الفكرة
احتفِظ بنافذة nums[left..right] ومجموعها. حرّك right خطوة واحدة في كل مرة، وأضف القيمة الجديدة. ما دام المجموع لا يقل عن target، تكون النافذة مرشحة: سجّل طولها، ثم احذف nums[left] وحرّك left إلى الأمام لترى ما إذا كانت نافذة أقصر لا تزال تحقق الشرط.
لماذا يمكن أن يغادر left نهائيًا؟ عندما تصل النافذة nums[left..right] إلى target لأول مرة، لم تحققه النافذة الأصغر nums[left..right-1]، لأن الحلقة كانت ستقلّصها في الخطوة السابقة. لذا فإن right هو أقرب نهاية ممكنة لهذا البدء، وأي نهاية لاحقة لا تعطي إلا مقطعًا فرعيًا أطول. لقد أعطى هذا البدء أفضل إجابة له. يتطلب هذا الاستدلال أن تكون القيم موجبة: فمع وجود عدد سالب، قد يكون مجموع نافذة أطول أكبر لاحقًا.
مع target = 15 و[4, 2, 9, 3, 7, 1, 5]: يرتفع المجموع إلى 4 ثم 6 ثم 15، فيُسجَّل الطول 3 ويُحذف 4 (11). تؤدي إضافة 3 إلى 14، وإضافة 7 إلى 21: سجّل الطول 4، واحذف 2 (19)، وسجّل الطول 3، واحذف 9 (10). تؤدي إضافة 1 و5 إلى 16: سجّل الطول 4، واحذف 3 (13). الإجابة هي 3.
تقع حلقة while داخل حلقة for، ومع ذلك يدخل كل فهرس النافذة مرة واحدة ويغادرها مرة واحدة، لذا يكون إجمالي العمل O(n). لا يُخزَّن سوى ثلاثة أعداد، لذا فالمساحة هي O(1).
الخوارزمية
- عيّن
left = 0وtotal = 0وbest = 0. - لكل قيمة
right، أضفnums[right]إلىtotal. - ما دام
total ≥ target، احتفظ بالقيمةright-left+1إذا كانت أكبر منbest، واطرحnums[left]ثم حرّكleftخطوة واحدة إلى اليمين. - أعِد
best، التي تظل 0 إذا لم يصل المجموع إلىtarget.
def minSubArrayLen(target, nums):
best = 0 # 0 means no window found yet
total = 0 # sum of nums[left .. right]
left = 0
for right in range(len(nums)):
total += nums[right]
# Shrink while the window still reaches target
while total >= target:
if best == 0 or right - left + 1 < best:
best = right - left + 1
total -= nums[left]
left += 1
return best
أخطاء شائعة وحالات حدّية
توجد معظم الأخطاء في خطوة تقليص النافذة وفي القيمة التي تعيدها عندما لا يصل أي مجموع إلى target.
- تقليص النافذة باستخدام
ifبدلًا منwhile. عندtarget = 12و[1, 1, 2, 3, 12]، تؤدي إضافة 12 إلى جعل المجموع 19. تسجّلifالطول 5، وتزيل قيمة واحدة ثم تتابع، لذلك لا يُقاس أبدًا طول النافذة[12]البالغ 1. أما الحلقة فتواصل الإزالة ما دام المجموع كافيًا. - تسجيل الطول بعد إزالة
nums[left]بدلًا من تسجيله قبل ذلك. يجب أن تكون النافذة التي تقيسها هي النافذة التي وصل مجموعها إلىtarget. - المقارنة باستخدام
>بدلًا من≥. يُحتسب المصفوفة الفرعية التي يساوي مجموعهاtarget: فالإجابة عن[3, 3, 3]عندما تكونtarget = 9هي 3، وليست 0. - إرجاع القيمة الحارسة. إذا بدأت
bestبقيمةn+1أو infinity، فحوّلها إلى 0 عندما لا يصل أي مجموع إلىtarget. - إعادة استخدام النافذة مع المصفوفات التي تحتوي على أصفار أو قيم سالبة. تعتمد هذه الطريقة على كون كل قيمة موجبة؛ يضمن هذا السؤال ذلك، لكن المسائل الأخرى لا تضمنه.
أسئلة شائعة4
ما هو التعقيد الزمني لمشكلة إيجاد أصغر مجموع لمصفوفة فرعية؟
يعمل حل النافذة المنزلقة بزمن O(n) ومساحة O(1). قد تبدو الحلقة الداخلية وكأنها تجعل التعقيد تربيعيًا، لكن left يتحرك إلى الأمام فقط، لذا لا يتقدم إلا n مرة كحد أقصى على امتداد التنفيذ كله. نسخة المجموع التراكمي هي O(n log n)، والتحقق من كل موضع بدء هو O(n²).
لماذا تتطلب نافذة الانزلاق أعدادًا موجبة؟
يجب أن يؤدي تصغير النافذة إلى خفض مجموعها، ويجب أن يؤدي تكبيرها إلى رفعه، وإلا فقد يؤدي حذف العنصر الأيسر إلى إسقاط بداية الإجابة. مع الأعداد السالبة، يختل هذا الترتيب. والحل المعتاد هو استخدام المجاميع التراكمية مع طابور مزدوج رتيب لنقاط البداية المرشحة، ويظل التنفيذ بزمن O(n).
لماذا نتعلم حل مجموع البادئات بتعقيد O(n log n) إذا كان هناك حل بتعقيد O(n)؟
غالبًا ما يطلبها القائمون على المقابلات بعد إجابة O(n). وهي تُظهر استخدامًا آخر للقيم الموجبة: فالمجاميع التراكمية مرتبة، لذا يحدد البحث الثنائي الموضع الذي يتجاوز فيه المجموع الجاري عتبةً للمرة الأولى. وتفيد هذه الأداة في مسائل أخرى أيضًا، مثل اختيار فهرس عشوائي باحتمال يتناسب مع وزنه.
هل يجب أن يكون مجموع المصفوفة الفرعية مساويًا للهدف تمامًا؟
لا. يُحتسب أي مجموع أكبر من target أو يساويه. عندما تكون قيمة target = 15، يكون مجموع النافذة 9، 3، 7 هو 19، ومع ذلك يظل طولها 3. إذا كنت تحتاج إلى مجموع مطابق تمامًا، فستظل النافذة صالحة للقيم الموجبة: قلّص النافذة ما دام المجموع أكبر من الهدف، وسجّل الطول فقط عندما يساويه.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def minSubArrayLen(target, nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
target = 15 nums = [4, 2, 9, 3, 7, 1, 5]
المتوقع
3