இரண்டு-சுட்டி நுட்பம் என்றால் என்ன?

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).

## எப்போது பயன்படுத்த வேண்டும் / சுறுசுறுப்புகள்

**வரிசைப்படுத்தப்பட்ட வரிசைகளுக்கு**, பலிந்திரம் சோதனைகளுக்கு, தலைகீழ் செய்யப்பட்டவற்றுக்கு, மற்றும் நகலை இடத்தில் அகற்றுவதற்கு சிறந்தது. வரிசை பெரும்பாலும் இணைக்கும் சுட்டி வகைக்கு வரிசைப்படுத்தப்பட்டிருக்க வேண்டும். சுட்டி எல்லைகள் மற்றும் வளையத்தின் நிபந்தனையுடன் (`lo < hi`)조심하세요.

## ஏன் முக்கியமாகக் கருதப்படுகிறது

இரண்டு-சுட்டி என்பது உயர்ந்த-அளவிலான நேர்காணல் வடிவங்களில் ஒன்றாகும்: இது கூடுதல் வளையங்களை ஒரு சுத்தமான நேரியல் ஸ்கேனாக மாற்றுகிறது.

இது brute force க்கு பதிலாக கட்டமைப்பைப் பயன்படுத்த உங்களுக்கு சொல்லிக்கொடுக்கிறது.

அதே கருத்து merge, பகிர்தல், மற்றும் merge sortன் கலப்பு நிலையை இயக்குகிறது.