用c语言哈希表实现two sums

题目描述：给定一个整数数组和一个目标值，在数组中找出和为目标值的两个数。

使用哈希表可以将时间复杂度降为O(n)，可以使用一个哈希表来存储数组中每个数的下标，然后遍历数组，对于每个数，查找哈希表中是否存在另一个数与它的和为目标值。

C语言代码实现：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;
    int hash[numsSize];
    memset(hash, -1, sizeof(hash)); // 初始化哈希表为-1
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i]; // 计算另一个数
        if (hash[complement] != -1) { // 在哈希表中查找另一个数
            result[0] = hash[complement];
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        hash[nums[i]] = i; // 将当前数存入哈希表
    }
    return result;
}

相关问题

用c语言哈希表法实现two sums完整代码

下面是用C语言哈希表法实现two sums的完整代码：

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

#define HASH_SIZE 1009

typedef struct ListNode {
    int val;
    int index;
    struct ListNode *next;
} ListNode;

ListNode *hashTable[HASH_SIZE];

void insert(int key, int index) {
    int h = abs(key) % HASH_SIZE;
    ListNode *node = hashTable[h];
    while (node != NULL) {
        if (node->val == key) {
            return;
        }
        node = node->next;
    }
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->val = key;
    newNode->index = index;
    newNode->next = hashTable[h];
    hashTable[h] = newNode;
}

int *twoSum(int *nums, int numsSize, int target) {
    for (int i = 0; i < HASH_SIZE; i++) {
        hashTable[i] = NULL;
    }
    for (int i = 0; i < numsSize; i++) {
        insert(nums[i], i);
    }
    int *result = (int *)malloc(2 * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int h = abs(complement) % HASH_SIZE;
        ListNode *node = hashTable[h];
        while (node != NULL) {
            if (node->val == complement && node->index != i) {
                result[0] = i;
                result[1] = node->index;
                return result;
            }
            node = node->next;
        }
    }
    return NULL;
}

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

代码中使用了链表来实现哈希表，哈希表大小为1009（一个质数），插入和查找的时间复杂度均为$O(1)$。在函数`twoSum`中，首先将所有数插入哈希表，然后遍历数组，对于每个数，计算它的补数，查找补数是否存在于哈希表中。如果存在，返回它们的下标即可。在函数结束时，需要释放动态分配的结果数组。

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)。