რა არის ორი-მაჩვენებლის ტექნიკა?

Question

Accepted Answer

**ორი-მაჩვენებლის** ტექნიკა იყენებს ორ ინდექსს, რომლებიც მოძრაობენ თანმიმდევრობით, ამ პრობლემების ამოსახსნელად ერთ პასში — მრავალი O(n²) brute-force გადაწყვეტის გადატანა **O(n)** ში.

## იდეა

შეინახეთ ორი მაჩვენებელი (ხშირად ბოლოებზე, ან ერთი ნელი და ერთი სწრაფი) და გადაიტანეთ ისინი პირობის მიხედვით, სამუშაოს შემცირება ხელახლა სკანირების გარეშე.

## მაგალითი: წყვილის პოვნა, რომელიც მიზნამდე იკრიბება დალაგებულ მასივში

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## სირთულე

- **დრო:** O(n). **სივრცე:** O(1).

## როდის გამოიყენება / სახიფათო ადგილები

მშვენიერია **დალაგებული მასივებისთვის**, პალინდრომის შემოწმებისთვის, შებრუნებისთვის და დუპლიკატების წაშლისთვის in place-ში. მასივი, ჩვეულებრივ, დალაგებული უნდა იყოს კონვერგირებული მაჩვენებლის ვარიანტისთვის. ფრთხილი იყავით მაჩვენებლის საზღვრებთან და ციკლის პირობასთან (`lo < hi`).

## რატომ არის ეს მნიშვნელოვანი

ორი მაჩვენებელი არის ერთ-ერთი ყველაზე მაღალი-leverage ინტერვიუს ნიმუში: იგი იკლებს nested ციკლებს სუფთა ხაზოვან სკანირებაში.

ეს ასწავლის თქვენ სტრუქტურის (როგორიცაა დახარისხება) ტყუილობას, ვიდრე brute force-ს.

იგივე იდეა ამოძრავებს სერვისებს, დაყოფას და merge sort-ის merge ნაბიჯს.