typedef struct HashNode {
int key;
int val;
} HashNode;
typedef struct HashMap {
int size;
HashNode** storage;
} HashMap;
HashMap* hash_create(int size);
void hash_destroy(HashMap* hashMap);
void hash_set(HashMap* hashMap, int key, int value);
HashNode* hash_get(HashMap* hashMap, int key);
HashMap* hash_create(int size){
HashMap* hashMap = malloc(sizeof(HashMap));
hashMap>size = size;
hashMap>storage = calloc(size, sizeof(HashNode*));
return hashMap;
}
void hash_destroy(HashMap* hashMap) {
for(int i=0; i < hashMap>size; i++) {
HashNode *node;
if((node = hashMap>storage[i])) {
free(node);
}
}
free(hashMap>storage);
free(hashMap);
}
void hash_set(HashMap *hashMap, int key, int value) {
int hash = abs(key) % hashMap>size;
HashNode* node;
while ((node = hashMap>storage[hash])) {
if (hash < hashMap>size  1) {
hash++;
} else {
hash = 0;
}
}
node = malloc(sizeof(HashNode));
node>key = key;
node>val = value;
hashMap>storage[hash] = node;
}
HashNode* hash_get(HashMap *hashMap, int key) {
int hash = abs(key) % hashMap>size;
HashNode* node;
while ((node = hashMap>storage[hash])) {
if (node>key == key) {
return node;
}
if (hash < hashMap>size  1) {
hash++;
} else {
hash = 0;
}
}
return NULL;
}
int* twoSum(int* nums, int numsSize, int target) {
HashMap* hashMap;
HashNode* node;
int rest, i;
// make the hashMap 2x size of the numsSize
hashMap = hash_create(numsSize * 2);
for(i = 0; i < numsSize; i++) {
rest = target  nums[i];
node = hash_get(hashMap, rest);
if (node) {
int* result = malloc(sizeof(int)*2);
result[0] = node>val + 1;
result[1] = i + 1;
hash_destroy(hashMap);
return result;
} else {
hash_set(hashMap, nums[i], i);
}
}
}
Accepted C solution of HashMap in 4ms


why "// make the hashMap 2x size of the numsSize"?
It's the load factor of a hashmap. I chose the load factor to be 0.5, which indicates how full the slots are.
For example, If I have 16 slots, I only use half of them which is 16 * 0.5 = 8.
AFAIK, Java's hashmap uses a load factor of 0.75, in the same case of which you use 16 * 0.75 = 12 slots.If you have a larger load factor, you use less memory but get more collisions. Otherwise, you have fewer collisions but use more memory. It's a tradeoff of implementation.

@dimoret
HashNode *node; if((node = hashMap>storage[i])) { free(node); }
This set of codes is no problem,node
just initialed byhashMap>storage[i]
, then checked whethernode
is null pointer, if not,free(node)
.


@ban2 The program is right. when collision occurs, the address will add one until program find a free space can hold number.

I got an AC in 3ms with this ugly code:
int* twoSum(int* nums, int numsSize, int target) { int _[100001] = {0}, *index_plus_one = _ + 50000; for (int i = 0; i < numsSize; i++) { int rest = target  nums[i]; if (index_plus_one[rest]) { int *ans = malloc(sizeof(int) * 2); ans[0] = i; ans[1] = index_plus_one[rest]  1; return ans; } else index_plus_one[nums[i]] = i + 1; } return NULL; }


What's the time complexity of the program? Should it be O(n^2) for the worst although the average running time seems much shorter? One test case is as follows: the first two number are the same, then increase them one by one, and the target is the sum of the last two numbers. eg:
[2,2,3,4,5,6,7,8,9] and the target is 17Also, I want to know what running time given by the test system means? Is it the average running time for 19 cases?