HOT100-1两数之和

题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

1. 解法

创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。这样的时间复杂度为O(1)。

2. 代码讲解

首先定义哈希表的结构：键值均为整数类型。再定义全局变量hashTable：

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

hashElement* hashTable = NULL;

然后写出函数的主框架，定义返回数组answerArray，在for循环中判断“ target - x是否已在哈希表中”，如果存在则将该键值对的值（能与当前数匹配的数在nums数组中的下标）传入anserArray[0]，再将i传入anserArray[1]；如果不存在则“将该键值对加入哈希表”。

需要注意的是：由于 hashTable 被定义为全局变量，如果不在for循环前清空哈希表的话，会导致多个测试用例之间存在数据残留，从而影响测试结果。在 LeetCode 的环境中，多个测试用例可能共享相同的全局变量，因此需要确保每次调用 twoSum 函数时，哈希表是干净的。

可以在for循环前加入hashTable = NULL;或者用HASH_CLEAR(hh, hashTable);清空。

或者也可以将hashTable设为局部变量，防止在Leetcode中出错：

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int i;
    int* anserArray = malloc(sizeof(int) * 2);
    hashElement* anserHash;

    hashTable = NULL;
    //HASH_CLEAR(hh, hashTable);

    for (i = 0;i < numsSize;i++)
    {
        int it = nums[i];

        if (findKey(target - it))
        {
            anserHash = findKey(target - it);
            anserArray[0] = anserHash->val;
            anserArray[1] = i;
            *returnSize = 2;
            return anserArray;
        }
        else
        {
            addHash(it, i);
        }
    }

    return NULL;

}

下面写两个函数用于实现“ target - x是否已在哈希表中”和“将该键值对加入哈希表”。

• “ target - x是否已在哈希表中”：

  先新建一个hashElement用于存放找到的键值对结果，然后用HASH_FIND_INT函数将找到的键值对结果存入hashElement中。

hashElement* findKey(int key) {
    hashElement* retHashElement;
    HASH_FIND_INT(hashTable, &key, retHashElement);
    return retHashElement;
}

• “将该键值对加入哈希表”：

  先新建一个hashElement用于接收传入的键值对，然后用HASH_ADD_INT函数将该键值对存入hashTable中。

void addHash(int key, int val) {
    hashElement* temp = malloc(sizeof(hashElement));
    temp->key = key;
    temp->val = val;
    HASH_ADD_INT(hashTable, key , temp);
}

3. 代码实现

可用于直接提交的代码：

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

hashElement* hashTable = NULL;

hashElement* findKey(int key) {
    hashElement* retHashElement;
    HASH_FIND_INT(hashTable, &key, retHashElement);
    return retHashElement;
}
void addHash(int key, int val) {
    hashElement* temp = malloc(sizeof(hashElement));
    temp->key = key;
    temp->val = val;
    HASH_ADD_INT(hashTable, key , temp);
}


int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int i;
    int* anserArray = malloc(sizeof(int) * 2);
    hashElement* anserHash;

    hashTable = NULL;

    for (i = 0;i < numsSize;i++)
    {
        int it = nums[i];
        
        if (findKey(target - it))
        {
            anserHash = findKey(target - it);
            anserArray[0] = anserHash->val;
            anserArray[1] = i;
            *returnSize = 2;
            return anserArray;
        }
        else
        {
            addHash(it, i);
        }
    }

    return NULL;

}

测试用完整代码：

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

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

hashElement* hashTable = NULL;

hashElement* findKey(int key) {
    hashElement* retHashElement;
    HASH_FIND_INT(hashTable, &key, retHashElement);
    return retHashElement;
}
void addHash(int key, int val) {
    hashElement* temp = malloc(sizeof(hashElement));
    temp->key = key;
    temp->val = val;
    HASH_ADD_INT(hashTable, key, temp);
}


int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int i;
    int* anserArray = malloc(sizeof(int) * 2);
    hashElement* anserHash;

    hashTable = NULL;

    for (i = 0;i < numsSize;i++)
    {
        int it = nums[i];

        if (findKey(target - it))
        {
            anserHash = findKey(target - it);
            anserArray[0] = anserHash->val;
            anserArray[1] = i;
            *returnSize = 2;
            return anserArray;
        }
        else
        {
            addHash(it, i);
        }
    }

    return NULL;

}


int main() {
    int nums[] = { 3, 3 };
    int target = 6;
    int returnSize = 0;

    int* ans = twoSum(nums, 2, target, &returnSize);
    if (returnSize == 2) {
        printf("%d %d\n", ans[0], ans[1]);
        free(ans);
    }
    else {
        printf("No solution found.\n");
    }

    return 0;
}