【Leetcode】1. Two Sum

题目地址https://leetcode.com/problems/two-sum/在一个数组中寻找两个数其和为给定的target返回这两个数的下标。思路是用一个哈希表存储数字和其对应的下标一旦发现target与某个数之差在哈希表里已经存在就返回两个下标。代码如下classSolution{public:vectorinttwoSum(vectorinta,intt){size_t na.size();unordered_mapint,intmp;mp.reserve(n);for(inti0;in;i){if(autoitmp.find(t-a[i]);it!mp.end())return{it-second,i};mp.try_emplace(a[i],i);}return{};}};时空复杂度O ( n ) O(n)O(n)。优化。把unordered_map的节点都开在一个monotonic上减少内存allocation的时间消耗同时更好的cache局部性。输入可以改为spanint。代码如下#includememory_resourceclassSolution{public:vectorinttwoSum(spaninta,intt){intna.size();static_assert((118)(sizeof(pairint,int)sizeof(void*))*10000);staticarraybyte,118buf;pmr::monotonic_buffer_resourcepool(buf.data(),buf.size(),pmr::null_memory_resource());pmr::unordered_mapint,intmp{pool};mp.reserve(n);for(inti0;in;i){if(autoitmp.find(t-a[i]);it!mp.end())return{it-second,i};mp.try_emplace(a[i],i);}return{};}};复杂度不变。