दुई-पॉइन्टर टेकनिक भनेको के हो?

Question

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`)।

## किन यो महत्त्वपूर्ण छ

दुई पॉइन्टर सबैभन्दा उच्च-लिभरेज अन्तर्वार्ता प्याटर्नहरू मध्ये एक हो: यसले नेस्टेड लूपहरूलाई स्वच्छ रेखीय स्क्यानमा संक्षिप्त गर्छ।

यसले तपाईंलाई ब्रुट फोर्सको सट्टा संरचना (जस्तै सज्जितता) को शोषण गर्न सिकाउँछ।

यही विचार एकीकरण, विभाजन, र मर्ज सर्टको मर्ज चरणलाई शक्तिशाली बनाउँछ।