leetcode两数之和c语言哈希表实现

以下是 LeetCode 上的「1. 两数之和」题目的 C 语言哈希表实现：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, j;
    int* result = (int*)malloc(sizeof(int) * 2);
    int* hashTable = (int*)malloc(sizeof(int) * numsSize);
    memset(hashTable, -1, sizeof(int) * numsSize);
    for(i = 0; i < numsSize; i++){
        int complement = target - nums[i];
        if(hashTable[complement] != -1){
            result[0] = hashTable[complement];
            result[1] = i;
            *returnSize = 2;
            free(hashTable);
            return result;
        }
        hashTable[nums[i]] = i;
    }
    free(hashTable);
    return NULL;
}

这个解法的基本思路是：使用哈希表以空间换时间，保存已经遍历过的数及其下标。对于每一个数，计算其与目标值之间的差值，然后在哈希表中查找是否存在该差值，如果存在则返回两个数的下标。时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。虽然空间复杂度较高，但是时间复杂度更低，是较优的解法。