two sums C语言代码哈希表

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

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

#define HASHSIZE 100

struct Node {
    int key;
    int val;
    struct Node* next;
};

struct HashTable {
    struct Node* nodes[HASHSIZE];
};

struct Node* createNode(int key, int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->key = key;
    node->val = val;
    node->next = NULL;
    return node;
}

void insert(struct HashTable* ht, int key, int val) {
    int index = abs(key) % HASHSIZE;
    struct Node* node = createNode(key, val);
    node->next = ht->nodes[index];
    ht->nodes[index] = node;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    struct HashTable ht;
    int* result = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;
    for (int i = 0; i < HASHSIZE; i++) {
        ht.nodes[i] = NULL;
    }
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int index = abs(complement) % HASHSIZE;
        struct Node* node = ht.nodes[index];
        while (node) {
            if (node->val == complement) {
                result[0] = node->key;
                result[1] = i;
                return result;
            }
            node = node->next;
        }
        insert(&ht, i, nums[i]);
    }
    return NULL;
}

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

这个代码实现了 `twoSum` 函数，该函数接受一个整数数组 `nums`，数组大小 `numsSize`，一个目标整数 `target` 和一个指向返回数组大小的整数指针 `returnSize`。函数返回一个整数指针，该指针指向一个包含两个索引的数组，这两个索引指向 `nums` 中相加等于 `target` 的两个数。

该代码使用哈希表来处理数组。我们首先创建一个大小为 `HASHSIZE` 的哈希表，每个节点包含一个键值对，其中键是数组中的索引，值是数组中的值。我们将每个节点插入到哈希表中，其中键是对当前节点值的哈希值。然后，我们遍历数组，对于每个值，我们计算其补数（即目标值与该值的差），并使用补数计算哈希值。我们在哈希表中查找补数，如果找到了，则返回当前索引和哈希表中补数对应的索引。

这个实现的时间复杂度为 O(n)，空间复杂度为 O(n)。