Two pointers tekniği nedir? Sıralı bir dizideki tekrarları yerinde nasıl silersiniz?

Two pointers, dizi üzerinde iki indeksin belirli bir kurala göre hareket ettirilmesidir. Ek bellek kullanmadan O(n) çözümler sağlar. İki yaygın biçimi vardır:

• Zıt uçlardan: biri baştan, biri sondan içe doğru (palindrom kontrolü, sıralı dizide hedef toplam).
• Aynı yönde, farklı hızda: biri okur, biri yazar (tekrar silme, sıfırları sona taşıma).

Problem: sıralı dizide tekrarları yerinde silme

[1,1,2,3,3] -> ilk 3 eleman [1,2,3], dönüş değeri 3.

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1                     # bir sonraki benzersiz elemanın yazılacağı yer
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

Zaman O(n), bellek O(1).

Zıt uç örneği: palindrom

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return False
        i += 1; j -= 1
    return True

Dizi sıralı ise iki işaretçi tekniği çoğu zaman hash map'e gerek bırakmaz; örneğin sıralı dizide toplamı hedefe eşit çift ararken toplam küçükse sol, büyükse sağ işaretçi hareket ettirilir.