3392. زیر مجموعه های طول سه را با یک شرط شمارش کنید

3392. زیر مجموعه های طول سه را با یک شرط شمارش کنید

مشکل: آسان

مباحث: Array

با توجه به یک آرایه عدد صحیح nums، تعداد فرعی را برگردانید¹ از طول 3 به گونه ای که جمع شماره های اول و سوم برابر است دقیقاً نیمی از شماره دوم.

مثال 1:

• ورودی: nums = [1,2,1,4,1]
• خروجی: 1
• توضیح: فقط فرعی [1,4,1] دقیقاً شامل 3 عنصر است که جمع شماره های اول و سوم با نیمی از تعداد میانی برابر است.

مثال 2:

• ورودی: nums = [1,1,1]
• خروجی: 0
• توضیح: [1,1,1] تنها زیر مجموعه طول 3 است. با این حال ، شماره های اول و سوم آن به نیمی از تعداد میانی اضافه نمی شود.

محدودیت ها:

• 3 <= nums.length <= 100
• -100 <= nums[i] <= 100

نکته:

1. محدودیت ها کوچک هستند. بررسی هر زیر مجموعه را در نظر بگیرید.

راه حل:

ما باید تعداد زیر مجموعه های طول 3 را که در آن جمع عناصر اول و سوم دقیقاً نیمی از عنصر دوم است ، حساب کنیم.

رویکرد

1. از طریق زیر مجموعه های احتمالی تکرار کنید: برای هر شاخص شروع از 0 تا n-3 (کجا n طول آرایه است) ، زیر را در نظر بگیرید که از آن شاخص با طول 3 شروع می شود.
2. برابری عنصر میانه را بررسی کنید: برای هر زیر مجموعه ، ابتدا بررسی کنید که آیا عنصر میانی یکنواخت است یا خیر. اگر عجیب باشد ، شرایط نمی تواند برآورده شود و ما به زیر مجموعه بعدی می رویم.
3. وضعیت جمع را بررسی کنید: اگر عنصر میانی یکنواخت است ، نیمی از آن را محاسبه کرده و بررسی کنید که آیا مبلغ عناصر اول و سوم Subarray برابر با این نیم ارزش است. اگر این کار را انجام دهید ، تعداد را افزایش دهید.

بیایید این راه حل را در PHP پیاده سازی کنیم: 3392. زیر مجموعه های طول سه را با یک شرط شمارش کنید

/**
 * @param Integer[] $nums
 * @return Integer
 */
function countSubarrays($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = array(1, 2, 1, 4, 1);
echo countSubarrays($nums1) . "\n"; // Output: 1

$nums2 = array(1, 1, 1);
echo countSubarrays($nums2) . "\n"; // Output: 0
?>

توضیح:

1. تکرار: حلقه از ابتدای آرایه تا جایی اجرا می شود که هنوز یک زیر مجموعه طول 3 شکل می گیرد. این تضمین می کند که ما همه زیر مجموعه های معتبر ممکن را بررسی می کنیم.
2. حتی چک کردن: عنصر میانی حتی باید برای جمع عناصر اول و سوم باشد که نیمی از آن را مساوی کند. این بررسی به سرعت زیر مجموعه های نامعتبر را رد می کند.
3. بررسی جمع: با محاسبه نیمی از عنصر میانه و مقایسه آن با مجموع عناصر اول و سوم ، ما به طور مؤثر تعیین می کنیم که آیا زیر مجموعه شرایط مورد نیاز را برآورده می کند یا خیر.

این رویکرد تضمین می کند که ما هر یک از زیر را در زمان خطی بررسی می کنیم و با توجه به محدودیت های مشکل ، راه حل را کارآمد می کنیم.

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید:

1. زیررویه: A subarray is a contiguous non-empty sequence of elements within an array. ↩