Competitive Programming Academy · पाठ

दिए गए Sum वाला Pair खोजना

O(n^2) brute force से बेहतर तरीका अपनाएँ

पाठ 2, कुल 4 में से13 चरण

दिए गए Sum वाला Pair खोजना, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 2वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

युग्म-योग समस्या

एक ऐरे और लक्ष्य दिए होने पर ऐसे दो मान खोजिए जो मिलकर उसे add करें। यह प्रतियोगिताओं में सबसे सामान्य प्रारंभिक अभ्यासों में से एक है। 🔍

बलपूर्वक जाँच का तरीका

सीधा समाधान दो नेस्टेड लूप की सहायता से हर युग्म को आज़माता है। यह काम करता है, लेकिन सभी युग्मों को जाँचने में O(n^2) समय लगता है और यह बहुत धीमा हो सकता है।

for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == target:
            return (i, j)

बलपूर्वक जाँच कहाँ विफल होती है

जब n लगभग 100000 हो, तो O(n^2) का अर्थ दस अरब जाँचें हैं और आपको TLE मिलेगा। सीमाएँ बता रही हैं कि आपको इससे तेज़ तरीका खोजना होगा।

पहले sort करें, फिर स्कैन करें

यदि आप पहले ऐरे को sort कर दें, तो दोनों सिरों से दो पॉइंटर एक ही पास में समस्या हल कर देते हैं। sort करने में O(n log n) लगता है और उसके बाद का स्कैन O(n) का होता है।

a.sort()
left, right = 0, len(a) - 1

लक्ष्य से तुलना करें

हर कदम पर a[left] + a[right] देखें। यह एक संख्या बिना किसी अनुमान के आपकी अगली चाल तय करती है।

total = a[left] + a[right]

सटीक मिलान: काम पूरा

यदि योग लक्ष्य के बराबर है, तो आपने युग्म ढूँढ़ लिया है। उसे तुरंत लौटाएँ, क्योंकि आपको केवल एक मान्य उत्तर चाहिए।

if total == target:
    return (left, right)

अन्यथा समायोजित करें

यदि योग बहुत छोटा है, तो बाएँ पॉइंटर को दाईं ओर ले जाएँ; यदि बहुत बड़ा है, तो दाएँ पॉइंटर को बाईं ओर ले जाएँ। क्रमबद्ध क्रम सुनिश्चित करता है कि हर चाल उपयोगी हो।

elif total < target:
    left += 1
else:
    right -= 1

कोई युग्म मौजूद नहीं है

यदि पॉइंटर बिना मिलान के एक-दूसरे को पार कर जाएँ, तो कोई मान्य युग्म मौजूद नहीं है। लूप का समाप्त होना ही पूरा उत्तर है।

हैश-सेट का विकल्प

यदि आपको मूल इंडेक्स सुरक्षित रखने हों, तो हैश सेट अधिक सरल है: हर मान के लिए जाँचें कि लक्ष्य में से वह मान घटाने पर मिली संख्या पहले देखी जा चुकी है या नहीं।

seen = set()
for x in a:
    if target - x in seen:
        # found
        pass
    seen.add(x)

अपनी विधि चुनें

जब ऐरे क्रमबद्ध हो या उसे क्रमबद्ध किया जा सकता हो, तब दो पॉइंटर का उपयोग करें; जब बिना क्रमबद्ध किए वास्तविक O(n) चाहिए या इंडेक्स सुरक्षित रखने हों, तब हैश सेट का उपयोग करें।

दोहराव पर ध्यान दें

यदि कोई मान खुद के साथ युग्म बना सकता है, तो सुनिश्चित करें कि आपके दोनों इंडेक्स अलग हों। एक त्वरित left != right या i != j जाँच इस गलती से बचाती है।

त्वरित जाँच

आप लक्ष्य के बराबर योग वाला युग्म खोजने की O(n^2) बलपूर्वक जाँच से बेहतर तरीका चाहते हैं।

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन

दो पॉइंटर की सहायता से पहले sort करें, फिर स्कैन करके O(n log n) में लक्ष्य युग्म खोजें; या जब इंडेक्स महत्वपूर्ण हों, तो O(n) के लिए हैश सेट का उपयोग करें। चुनाव सीमाओं के आधार पर करें। ✅

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 30
पाठ: 120

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “दिए गए Sum वाला Pair खोजना” पाठ निःशुल्क है?

हाँ—“दिए गए Sum वाला Pair खोजना” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“दिए गए Sum वाला Pair खोजना” में मैं क्या सीखूँगा?

O(n^2) brute force से बेहतर तरीका अपनाएँ आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 2वाँ पाठ है।

“दिए गए Sum वाला Pair खोजना” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

← Competitive Programming Academy पर वापस जाएँ