two sums C语言代码哈希表

以下是使用哈希表实现 Two Sum 问题的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashNode;

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    HashNode* hashTable = NULL;
    HashNode* node = NULL;
    int i;
    int* result = (int*) malloc(2 * sizeof(int));
    *returnSize = 2;
    for (i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        HASH_FIND_INT(hashTable, &complement, node);
        if (node) {
            result[0] = node->val;
            result[1] = i;
            return result;
        }
        node = (HashNode*) malloc(sizeof(HashNode));
        node->key = nums[i];
        node->val = i;
        HASH_ADD_INT(hashTable, key, node);
    }
    return NULL;
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    int* result = twoSum(nums, 4, target, &returnSize);
    if (result != NULL) {
        printf("[%d, %d]\n", result[0], result[1]);
        free(result);
    }
    return 0;
}

这个代码的思路是使用哈希表来优化查找过程。我们遍历一次数组，同时在哈希表中存储每个元素的值和下标，然后在每次遍历时，用目标值减去当前元素的值，得到差值，然后在哈希表中查找这个差值是否存在，如果存在就说明找到了一组符合条件的元素对，否则就把当前元素的值和下标存储到哈希表中。这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)。