# How can I do it faster (20ms)

• I iterate over the array, and I use the hash table to find ( target -nums[i])
If there is any, then is done.
hash table provide average O(1) complexity so I think this is quite fast.
Is there other faster way? I saw some posts using map to solve this, why is it faster?

``````class Solution{
public:
typedef struct pair {
public:
int index;
int content;
}myPair;

vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
hash myHash(nums);
myPair* resPair=NULL;
int i = 0;
for (i = 0; i <nums.size(); i++) {
resPair = myHash.findPair(target - nums[i]);
if (resPair == NULL)
continue;
else if (resPair->index == i)
continue;
else
break;

}

if (resPair == NULL || resPair->index == i)
{
res.push_back(3); res.push_back(4);
}

res.push_back(i + 1);
res.push_back((resPair->index) + 1);
sort(res.begin(), res.end());

return res;
}

class hash {
public:
hash(vector<int>& nums) {
bucketSize = nums.size();
hashTable.reserve(bucketSize);
for (int i = 0; i < nums.size(); i++) {
vector<myPair> tmp;
hashTable.push_back(tmp);
}

for (int i = 0; i <nums.size(); i++)
{
insertTarget(nums[i], i);
}
}

~hash() {}

myPair* findPair(int num) {

int k = getKey(num);

return linearSearch(k, num);

}

myPair* linearSearch(int k, int num) {

for (int i = 0; i <hashTable[k].size(); i++)
if (hashTable[k][i].content == num)
return &hashTable[k][i];
return NULL;
}

int getKey(int target) {
if (target < 0)
target = 0 - target;
return (target) % bucketSize;

}

void insertTarget(int number, int index) {
int k = getKey(number);
myPair newPair;
newPair.content = number;
newPair.index = index;
hashTable[k].push_back(newPair);
}

private:
vector<vector<myPair>> hashTable;
int bucketSize;
};
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.