0001 两数之和

简单 哈希

算法思路

简单而言，我们需要在一个整数数组中找到特定的两个数 a b，使得 a b 之和为目标 target。

最直接的解法显然遍历每个整数对并计算两者之和，当结果满足条件时结束并返回。显然，暴力计算的时间复杂度为 \(O(n^2)\)。

初见此题，我在排除暴力计算后，第一反应是先将数组排序，然后在大概 target/2 处创建两个指针分别向两侧遍历，直到找到满足条件的整数对。 这样寻找整数对的时间复杂度简化为\(O(n)\)。 显然，上述思考引入新的问题：排序。对于整数数组排序，不可避免的时间复杂度来到了\(O(nlogn)\)。

因此，思路逐渐清晰：我们需要在不排序的前提下，对于整数数组中的一个数 a，快速（\(O(1)\)复杂度内）确定数组中是否存在一个值为 target-a 的数。 从而得出方法：哈希。最终时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)。

代码实现

two-sum.c

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

/*
作者：力扣官方题解
链接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

知识补充

上述代码使用了 uthash 库（一个用 C 宏实现的哈希表）。

对于结构体 hashTable，其中的 UT_hash_handle hh 是 uthash 库要求必须添加的成员。UT_hash_handle 一个内部结构体类型，它包含了用于维护哈希表的前驱、后继、哈希值、桶索引等指针信息。这个成员使得该结构体可以被 uthash 的宏管理。

HASH_FIND_INT(hashtable, &ikey, tmp);：这是一个 uthash 提供的宏，用于在哈希表中查找键为 ikey 的元素。

HASH_ADD_INT(hashtable, key, tmp);：将新节点 tmp 添加到哈希表中。