Python में Two Sum Algorithm
Target sum बनाने वाले दो values खोजें।
में Two Sum Algorithm क्या है?
समस्या क्या है
कीमतों की लिस्ट और एक बजट दिया है, कौन से दो आइटम मिलकर ठीक बजट के बराबर हैं? हर जोड़ी जाँचना काम करता है, लेकिन इसमें करीब n² / 2 तुलनाएँ लगती हैं। जो आप पहले देख चुके हैं उसे याद रखने से यह एक pass में हो सकता है।
ऐसे समझें
Two Sum ऐसा है जैसे तय बजट लेकर ख़रीदारी करना। हर price tag देखकर आप हिसाब लगाते हैं कि कितने पैसे और चाहिए, फिर अपनी पर्ची देखते हैं: क्या मैंने ठीक इसी दाम की कोई चीज़ पहले देखी है? हाँ, तो जोड़ी मिल गई। नहीं, तो यह दाम और उसकी जगह पर्ची पर लिखकर आगे बढ़ जाते हैं।
complement = target - value🤔 बाक़ी बचा दामif complement in seen:📋 क्या यह दाम मेरी पर्ची पर पहले से है?return [seen[complement], index]🛍️ जोड़ी मिल गई: दोनों की जगहseen[value] = index✍️ यह दाम और इसकी जगह लिखिए, फिर आगे बढ़िएTwo Sum समस्या लिस्ट में उन दो संख्याओं की positions माँगती है जिनका जोड़ target के बराबर हो; देखी हुई वैल्यू की डिक्शनरी इसे एक pass में, O(n) समय में हल कर देती है।
मुख्य बातें
complement = target - valueवह वैल्यू है जो जोड़ी पूरी करेगी।seenपहले देखी गई हर वैल्यू को उसके index से जोड़ता है, इसलिए lookup तेज़ हैं।if complement in seen:पहले की वैल्यू में पार्टनर ढूँढता है।seen[value] = indexजाँच के बाद सेव होता है, इसलिए कोई वैल्यू ख़ुद से जोड़ी नहीं बनाती।- 9 के लिए, वैल्यू 7 को index 0 पर अपना पार्टनर 2 मिलता है, जिससे
[0, 1]मिलता है।
इसका उपयोग कब करें?
- दिए गए जोड़ या अंतर वाली जोड़ियाँ ढूँढना।
- Hash table से मेमोरी के बदले स्पीड लेना सीखना।
- इंटरव्यू का बहुत आम सवाल और 3-Sum जैसी समस्याओं का आधार।
कब ज़रूरत नहीं
- Sorted इनपुट जहाँ मेमोरी कम हो: दोनों सिरों से two pointers कोई अतिरिक्त मेमोरी नहीं लेते।
- आपको सिर्फ़ एक नहीं, हर जोड़ी चाहिए: पहले मैच पर लौटने की जगह नतीजे इकट्ठे कीजिए।
उदाहरण कोड
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
अपेक्षित आउटपुट
[0, 1]
यह कैसे काम करता है
Complement O(1) में lookup होता है: कुल समय O(n) और memory O(n) है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
जाँचने से पहले सेव करना
कोई वैल्यू ख़ुद से जोड़ी बना सकती है, जैसे सिर्फ़ एक 3 होने पर भी 3 + 3 = 6।
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
सभी चैलेंज