Two Pointers

अभिसरण या पीछा

विपरीत सिरे: left और right एक-दूसरे की ओर (sorted two-sum, palindrome, container with most water)। एक ही दिशा: धीमा और तेज़ पॉइंटर (जगह पर duplicate हटाना, cycle पहचान)। O(n^2) को O(n) बनाता है।

Sorted two-sum

यदि योग बहुत छोटा है, केवल left ऊपर करना मदद करेगा; बहुत बड़ा तो केवल right नीचे।

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

त्वरित जाँच: विपरीत-सिरे two-pointer तरकीब को array चाहिए...

• Sorted
• सभी धनात्मक
• सम लंबाई