একটি হ্যাশ ম্যাপ (অভিধান) 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([, , , ], )