हॅश मॅप (डिक्शनरी) O(1) सरासरी शोध, सन्निहित आणि हटवण्याचा वेळ देते. O(n) मेमरी गतीसाठी व्यापार करून अनेक O(n²) अल्गोरिदम O(n) मध्ये रूपांतरित करते आणि पुनरावृत्त स्कॅन तात्काळ शोधांसह बदलते.
कल्पना
प्रत्येक वेळी यादीत शोध करण्याऐवजी, दिलेली मूल्ये हॅश मॅप मध्ये साठवा आणि सदस्यता स्थिर वेळेत तपासा.
उदाहरण: O(n) मध्ये दोन-बेरीज
python
():
seen = {}
i, x (nums):
need = target - x
need seen:
(seen[need], i)
seen[x] = i
two_sum([, , , ], )