المؤشرات المزدوجة والنافذة المنزلقة

هذان النمطان وحدهما يحلان نسبة كبيرة من مسائل المصفوفات والسلاسل النصية. يستبدلان الحلقات المتداخلة بحلول أنيقة بتعقيد O(n).

نمط المؤشرات المزدوجة

الفكرة بسيطة: استخدم مؤشرين يتحركان عبر هيكل البيانات، عادةً من الطرفين المتقابلين أو بسرعات مختلفة.

ثلاثة أشكال:

1. الاتجاه المعاكس (التقارب)

يُستخدم عندما تحتاج لإيجاد أزواج أو فحص التماثل.

# الحاوية ذات أكبر ماء
def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

# مجموع اثنين (مصفوفة مرتبة)
def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        elif total < target:
            left += 1
        else:
            right -= 1

2. نفس الاتجاه (سريع/بطيء)

يُستخدم لإزالة التكرارات أو التقسيم أو مسائل القوائم المترابطة.

# إزالة التكرارات من مصفوفة مرتبة (في المكان)
def remove_duplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

3. ثلاثة مؤشرات

توسيع للمؤشرات المزدوجة لمسائل مثل 3Sum.

# 3Sum: إيجاد جميع الثلاثيات التي مجموعها صفر
def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # تخطي التكرارات
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1  # تخطي التكرارات
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

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

نافذة تنزلق عبر مصفوفة/سلسلة نصية، تتوسع أو تنكمش لإيجاد المصفوفات الفرعية المثلى.

نافذة بحجم ثابت

# أقصى مجموع لمصفوفة فرعية بحجم k
def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

نافذة بحجم متغير

# أطول سلسلة فرعية بدون أحرف مكررة
def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

# أصغر نافذة فرعية
def min_window(s, t):
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    left = start = 0
    min_len = float('inf')
    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
        while missing == 0:
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return s[start:start + min_len] if min_len != float('inf') else ""

دليل التعرف على الأنماط

الإشارة	النمط	التعقيد الزمني
"مصفوفة مرتبة + إيجاد زوج"	مؤشرات مزدوجة (معاكسة)	O(n)
"فحص التناظر"	مؤشرات مزدوجة (معاكسة)	O(n)
"إزالة التكرارات في المكان"	مؤشرات مزدوجة (نفس الاتجاه)	O(n)
"مصفوفة فرعية بحجم K"	نافذة منزلقة ثابتة	O(n)
"أطول/أقصر سلسلة فرعية بشرط"	نافذة منزلقة متغيرة	O(n)
"3Sum / 4Sum"	ترتيب + مؤشرات مزدوجة	O(n^2) / O(n^3)

---

التالي: سنغطي البحث الثنائي والخوارزميات الجشعة -- أنماط تحسّن اتخاذ القرارات. :::