ENDEAR
ابدأ مجاناً
خوارزميةمجاني

النافذة المنزلقة

اعثر على أكبر مجموع لـ k أعداد متتالية دون إعادة جمع النافذة كلها في كل مرة.

الزمن
O(n)
الذاكرة
O(1)

تتبّعها خطوة بخطوة

الخطوة 1 من 9
1function maxWindowSum(nums, k) {2  let total = 0;3  for (let i = 0; i < k; i++) total += nums[i];4  let best = total;5  for (let i = k; i < nums.length; i++) {6    total += nums[i] - nums[i - k];7    best = Math.max(best, total);8  }9  return best;10}
k
= 3
total
= 8
  1. 2
  2. 1
  3. 5
  4. 1
  5. 3
  6. 2

نجمع النافذة الأولى المكوّنة من k = 3 أعداد: total = 8.

كيف تعمل

اجمع أول k أعداد مرة واحدة. ثم حرّك النافذة خطوة خطوة: أضف العدد الذي يدخل من اليمين واطرح العدد الذي يخرج من اليسار. تحديث كل نافذة يكلّف O(1)، لذا يكون المرور كله خطّياً.