Əsas məzmuna keçin

Two Pointers nədir?

Two Pointers sadə, amma güclü bir algoritmik texnikadır. Bu texnikada data strukturu üzərində (array, list, string) iki pointer (indeks) istifadə edilir. Bu pointerlər ya bir-birinə doğru, ya da eyni istiqamətdə hərəkət edərək məsələni daha səmərəli həll edir.

Nə vaxt istifadə edilir?​

1. Sıralanmış məlumatlar​

Array və ya list artıq sıralanmışdırsa (və ya sıralana bilərsə), two pointers cütləri və ya aralıqları tapmaq üçün çox səmərəlidir.

  • Nümunə: Sıralanmış array-də cəmi müəyyən ədədə bərabər olan iki ədəd tapmaq

2. Cütlər və ya alt-arraylar​

Məsələ iki element, alt-array və ya aralıqlarla bağlı olduqda.

  • Nümunə: Təkrarlanmayan simvolları olan ən uzun alt-string, palindrom yoxlamaq

3. Sliding Window məsələləri​

Şərtlərə əsasən böyüyən/kiçilən element pəncərəsini saxlamaq lazım olduqda.

  • Nümunə: Cəmi K-dan böyük olan ən kiçik alt-array tapmaq

4. Linked List-lər (Slow-Fast pointers)​

Cycle aşkarlamaq, orta node tapmaq və ya palindrom xüsusiyyətini yoxlamaq üçün.

  • Nümunə: Floyd's Cycle Detection Algorithm

Əsas strategiyalar​

1. Daxilə doğru hərəkət (Inward Traversal)​

  • Pointerlər data strukturunun əks uclarından başlayır
  • Mərkəzə doğru hərəkət edir
  • Müəyyən şərt ödənənə qədər davam edir
[left →  • • • • • •  ← right]

2. Eyni istiqamətdə hərəkət (Unidirectional Traversal)​

  • Hər iki pointer eyni ucdan (adətən başlanğıcdan) başlayır
  • Eyni istiqamətdə hərəkət edir
  • Bir pointer məlumat axtarır, digəri məlumatı saxlayır
[left → right → • • • • • •]

3. Mərhələli hərəkət (Staged Traversal)​

  • Əvvəl bir pointer hərəkət edir
  • Müəyyən şərt ödəndikdə ikinci pointer aktivləşir
  • Hər pointer fərqli məqsədə xidmət edir

Üstünlükləri​

  • Zaman mürəkkəbliyi: Adətən O(n²)-dən O(n)-ə endirir
  • Yaddaş mürəkkəbliyi: Əlavə data strukturuna ehtiyac olmur (O(1) yaddaş)
  • Sadəlik: Başa düşmək və implement etmək asandır

Populyar məsələ nümunələri​

  • Two Sum (sıralanmış array)
  • Three Sum / Four Sum
  • Trapping Rain Water
  • Container With Most Water
  • Palindrome yoxlamaq
  • Sıfırları sona köçürmək

Nümunə Problemlər və Həllər​

1. İki Ədədin Cəmi (Two Sum - Sorted Array)​

Problem: Sıralanmış bir array verilir. Array-də cəmi hədəf dəyərə (target) bərabər olan iki ədədi tapın.

Həll:

Koda bax
public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        
        if (sum == target) {
            return new int[] {left + 1, right + 1}; // 1-indexed
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return new int[] {-1, -1}; // No solution found
}

2. Palindrome Yoxlanışı​

Problem: Verilmiş string-in palindrome olub-olmadığını yoxlayın.

Həll:

Koda bax
public boolean isPalindrome(String s) {
    // Alphanumeric olmayan simvolları təmizləyək və hər şeyi kiçik hərfə çevirək
    s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
    
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

3. Sıralanmış Array-dən Dublikatların Silinməsi​

Problem: Sıralanmış bir array verilir. Dublikatları silin və yeni uzunluğu qaytarın.

Həll:

Koda bax
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    
    int i = 0; // Slow pointer
    
    for (int j = 1; j < nums.length; j++) { // Fast pointer
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    
    return i + 1; // New length
}

4. Container With Most Water​

Problem: n uzunluqlu bir array verilir, hər element i mövqeyində olan sütunun hündürlüyünü göstərir. Ən çox su tuta bilən konteynerin sahəsini tapın.

Həll:

Koda bax
public int maxArea(int[] height) {
    int maxArea = 0;
    int left = 0;
    int right = height.length - 1;
    
    while (left < right) {
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxArea = Math.max(maxArea, width * h);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

Complexity​

  • Zaman Mürəkkəbliyi: Əksər hallarda O(n), burada n array və ya string-in uzunluğudur
  • Yaddaş Mürəkkəbliyi: Adətən O(1), çünki yalnız bir neçə əlavə dəyişən istifadə olunur