Τι είναι η τεχνική δύο δεικτών;

Question

IT Interview Practice · Accepted Answer

Η τεχνική **δύο δεικτών** χρησιμοποιεί δύο ευρετήρια που κινούνται μέσω μιας ακολουθίας για να λύσουν προβλήματα σε ένα μόνο πέρασμα — μετατρέποντας πολλές λύσεις O(n²) βίας σε **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).

## Πότε να χρησιμοποιήσετε / Παγίδες

Πολύ καλό για **ταξινομημένους πίνακες**, ελέγχους παλινδρόμου, αντιστροφή και κατάργηση διπλοτύπων στη θέση. Ο πίνακας συχνά πρέπει να είναι ταξινομημένος για την παραλλαγή συγκλίνοντων δεικτών. Προσέξτε τα όρια δεικτών και την συνθήκη βρόχου (`lo < hi`).

## Γιατί έχει σημασία

Οι δύο δείκτες είναι ένα από τα πιο υψηλής απόδοσης πρότυπα συνεντεύξεων: καταρρακώνει τους ένθετους βρόχους σε μια καθαρή γραμμική σάρωση.

Σας διδάσκει να εκμεταλλεύεστε τη δομή (όπως η ταξινόμηση) αντί για βίαιη δύναμη.

Η ίδια ιδέα τροφοδοτεί τη συγχώνευση, τη διαμέρισμα και το βήμα συγχώνευσης της ταξινόμησης συγχώνευσης.

Η ιδέα

Παράδειγμα: ζευγοποίηση που αθροίζεται σε στόχο σε ταξινομημένο πίνακα

Πολυπλοκότητα

Πότε να χρησιμοποιήσετε / Παγίδες

Γιατί έχει σημασία

Σχετικές ερωτήσεις