يعد العثور على مصفوفة فرعية بمجموع معين مشكلة شائعة تظهر غالبًا في مقابلات البرمجة والبرمجة التنافسية. يمكن حل هذه المشكلة باستخدام تقنيات مختلفة، ولكل منها مقايضاتها الخاصة فيما يتعلق بالتعقيد الزمني والتعقيد المكاني. في هذه المقالة، سنستكشف طرقًا متعددة لحل مشكلة العثور على مصفوفة فرعية بمجموع معين في Java.

بيان المشكلة

بالنظر إلى مصفوفة من الأعداد الصحيحة والمجموع المستهدف، ابحث عن مصفوفة فرعية مستمرة في المصفوفة تضيف ما يصل إلى المجموع المحدد. يمكن تقسيم المشكلة إلى قسمين رئيسيين:

1. المصفوفة الفرعية ذات الأرقام الموجبة: تحتوي المصفوفة على أرقام موجبة فقط.
2. المصفوفة الفرعية ذات الأرقام المختلطة: تحتوي المصفوفة على أرقام موجبة وسالبة.

دعونا نستكشف طرقًا مختلفة لحل هذه المتغيرات.

المنهج 1: استخدام القوة الغاشمة

يتضمن نهج القوة الغاشمة التحقق من جميع المصفوفات الفرعية الممكنة وحساب مجموعها لمعرفة ما إذا كان أي منها يساوي المجموع المستهدف. يعمل هذا الأسلوب مع كلا المتغيرين ولكنه غير فعال بالنسبة للمصفوفات الكبيرة بسبب التعقيد الزمني التربيعي.

تطبيق

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start 
الإخراج
Subarray found from index 1 to 3

تحليل

• تعقيد الوقت: O(n²) بسبب تكرار الحلقتين المتداخلتين عبر المصفوفة.
• تعقيد المساحة: O(1) حيث لا يتم استخدام مساحة إضافية خارج مصفوفة الإدخال.

المنهج 2: استخدام النافذة المنزلقة

يعتبر أسلوب النافذة المنزلقة فعالاً بالنسبة للمصفوفات التي تحتوي على أرقام موجبة فقط. تتضمن هذه التقنية الحفاظ على نافذة من العناصر التي تضيف ما يصل إلى المبلغ المستهدف. يتم توسيع النافذة بإضافة عناصر حتى يتجاوز المجموع الهدف، ويتم تقليصها عن طريق إزالة العناصر من البداية حتى يصبح المجموع أقل من أو يساوي الهدف.

تطبيق

public class SubarraySumSlidingWindow {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int start = 0;
    int currentSum = 0;

    for (int end = 0; end  targetSum && start 
الإخراج
Subarray found from index 1 to 3

تحليل

• تعقيد الوقت: O(n) حيث تتم معالجة كل عنصر مرتين على الأكثر.
• تعقيد المساحة: O(1) نظرًا لعدم الحاجة إلى مساحة إضافية.