Two Sum

TwoSum.c

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct hashTableNode {
	int val;
	int idx;
	struct hashTableNode* next;
} hashTableNode;

void initHashTable(hashTableNode*** hash, int hashTableSize) {
	int i;
	(*hash) = (hashTableNode**)malloc(hashTableSize*sizeof(hashTableNode*));
	for (i = 0; i < hashTableSize; i++) {
		(*hash)[i] = NULL;
	}
}

void insertHashTable(hashTableNode** hash, int hashTableSize, int val, int idx) {
	hashTableNode* tmp = (hashTableNode*)malloc(sizeof(hashTableNode));
	hashTableNode* node;
	int hashTableIdx = val % hashTableSize;
	hashTableIdx = hashTableIdx >= 0 ? hashTableIdx : hashTableIdx + hashTableSize;
	tmp->val = val;
	tmp->idx = idx;
	tmp->next = NULL;
	if (hash[hashTableIdx] == NULL) {
		hash[hashTableIdx] = tmp;
		return;
	}
	for (node = hash[hashTableIdx]; node->next != NULL; node = node->next);
	node->next = tmp;
}

int getHashTable(hashTableNode** hash, int hashTableSize, int val) {
	int hashTableIdx = val % hashTableSize;
	hashTableNode* node;
	hashTableIdx = hashTableIdx >= 0 ? hashTableIdx : hashTableIdx + hashTableSize;
	for (node = hash[hashTableIdx]; node != NULL; node = node->next) {
		if (node->val == val) {
			return node->idx;
		}
	}
	return -1;
}

void freeHashTableNode(hashTableNode** node) {
	if ((*node)->next != NULL) {
		freeHashTableNode(&((*node)->next));
	}
	free(*node);
	*node = NULL;
}

void freeHashTable(hashTableNode** hash, int hashTableSize) {
	int i;
	for (i = 0; i < hashTableSize; i++) {
		if (hash[i] != NULL) {
			freeHashTableNode(hash + i);
		}
	}
}

int* twoSum(int* nums, int numsSize, int target) {
	int i, idx, tmp;
	hashTableNode** hash;
	int* ans = (int*)malloc(2 * sizeof(int));
	initHashTable(&hash, numsSize);
	ans[0] = ans[1] = 0;
	for (i = 0; i < numsSize; i++) {
		insertHashTable(hash, numsSize, nums[i], i);
	}
	for (i = 0; i < numsSize; i++) {
		idx = getHashTable(hash, numsSize, target-nums[i]);
		if (idx >= 0 && idx != i) {
			ans[0] = i+1;
			ans[1] = idx+1;
			if (ans[0] > ans[1]) {
				tmp = ans[0];
				ans[0] = ans[1];
				ans[1] = tmp;
			}
		}
	}
	freeHashTable(hash, numsSize);
	return ans;
}