Python एल्गोरिदम

Python में Two Sum Algorithm

Target sum बनाने वाले दो values खोजें।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में Two Sum Algorithm क्या है?

समस्या क्या है

कीमतों की लिस्ट और एक बजट दिया है, कौन से दो आइटम मिलकर ठीक बजट के बराबर हैं? हर जोड़ी जाँचना काम करता है, लेकिन इसमें करीब n² / 2 तुलनाएँ लगती हैं। जो आप पहले देख चुके हैं उसे याद रखने से यह एक pass में हो सकता है।

ऐसे समझें

Two Sum ऐसा है जैसे तय बजट लेकर ख़रीदारी करना। हर price tag देखकर आप हिसाब लगाते हैं कि कितने पैसे और चाहिए, फिर अपनी पर्ची देखते हैं: क्या मैंने ठीक इसी दाम की कोई चीज़ पहले देखी है? हाँ, तो जोड़ी मिल गई। नहीं, तो यह दाम और उसकी जगह पर्ची पर लिखकर आगे बढ़ जाते हैं।

बजट वाली ख़रीदारी से code तक
complement = target - value🤔 बाक़ी बचा दाम
if complement in seen:📋 क्या यह दाम मेरी पर्ची पर पहले से है?
return [seen[complement], index]🛍️ जोड़ी मिल गई: दोनों की जगह
seen[value] = index✍️ यह दाम और इसकी जगह लिखिए, फिर आगे बढ़िए
हर जोड़ी जाँचने की बजाय बाक़ी बचा दाम पर्ची में देखिए।
एक वाक्य में

Two Sum समस्या लिस्ट में उन दो संख्याओं की positions माँगती है जिनका जोड़ target के बराबर हो; देखी हुई वैल्यू की डिक्शनरी इसे एक pass में, O(n) समय में हल कर देती है।

मुख्य बातें

  1. complement = target - value वह वैल्यू है जो जोड़ी पूरी करेगी।
  2. seen पहले देखी गई हर वैल्यू को उसके index से जोड़ता है, इसलिए lookup तेज़ हैं।
  3. if complement in seen: पहले की वैल्यू में पार्टनर ढूँढता है।
  4. seen[value] = index जाँच के बाद सेव होता है, इसलिए कोई वैल्यू ख़ुद से जोड़ी नहीं बनाती।
  5. 9 के लिए, वैल्यू 7 को index 0 पर अपना पार्टनर 2 मिलता है, जिससे [0, 1] मिलता है।

इसका उपयोग कब करें?

  • दिए गए जोड़ या अंतर वाली जोड़ियाँ ढूँढना।
  • Hash table से मेमोरी के बदले स्पीड लेना सीखना।
  • इंटरव्यू का बहुत आम सवाल और 3-Sum जैसी समस्याओं का आधार।

कब ज़रूरत नहीं

  • Sorted इनपुट जहाँ मेमोरी कम हो: दोनों सिरों से two pointers कोई अतिरिक्त मेमोरी नहीं लेते।
  • आपको सिर्फ़ एक नहीं, हर जोड़ी चाहिए: पहले मैच पर लौटने की जगह नतीजे इकट्ठे कीजिए।

उदाहरण कोड

कोड चलाएँ →
main.py
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))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

[0, 1]

यह कैसे काम करता है

Complement O(1) में lookup होता है: कुल समय O(n) और memory O(n) है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

जाँचने से पहले सेव करना

कोई वैल्यू ख़ुद से जोड़ी बना सकती है, जैसे सिर्फ़ एक 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 रिव्यू के साथ।

सभी चैलेंज