# 6ms C++ O(n) Binary multiplicative hashing with linear probing

• ``````class Solution {
public:

vector<int> twoSum(vector<int>& nums, int target) {
random_device rd;
mt19937 gen(rd());
unsigned int salt = gen();
int numSize = nums.size();
int hashBits = ceil(log2(numSize));
int hashSize = exp2(hashBits);
int hashShift = sizeof(int)*8 - hashBits;
int hashTable[hashSize];
int numIndex[hashSize];
bool hashTableFill[hashSize] = {false};

auto hashFunc = [&] (int value) -> int {
int hashIndex = (unsigned int)value*salt >> hashShift; //Binary multiplicative hashing
while(hashTableFill[hashIndex] && hashTable[hashIndex] != value) {
hashIndex++; // linear probing
if(hashIndex >= hashSize) hashIndex = 0;
}
return hashIndex;
};

auto insert = [&] (int value, int index) {
int hashIndex = hashFunc(value);
hashTableFill[hashIndex] = true;
hashTable[hashIndex] = value;
numIndex[hashIndex] = index;
};

auto search = [&] (int value) -> int {
int hashIndex = hashFunc(value);
if(hashTableFill[hashIndex]){
return numIndex[hashIndex];
} else {
return -1;
}
};

vector<int> result(2);
for(int i = 0; i<numSize; i++){
int diff = target - nums[i];
int searchID = search(diff);
if(searchID>=0){
result[0] = searchID;
result[1] = i;
return result;
}
insert(nums[i], i);
}
return result;
}
};
``````

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