力扣刷题——双数之和

很多人去力扣刷题都是数组的第一题，也就是双数之和，相信这也是很多人劝退题目，甚至对自己学过的知识产生了怀疑，这真的是我学完C语言，Java，Python或C++之后能做出来的题目吗？直接劝退了很多人，这里就对这一道劝退题目进行分析和解答。

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
• 只会存在一个有效答案

2、分析

看到题目的时候，直接狂喜，因为题目看着很“简单”，直接两次for循环，找到数组的两个元素相加等于目标值然后返回其数组元素对应下标就完成题目要求了。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){ 
    int* ret = malloc(sizeof(int) * 2);
    for(int i = 0;i < numsSize;i++)
    {
        for(int j = i + 1;j < numsSize;j++)
        {
            if(nums[i] + nums[j] == target)
            {
                *returnSize = 2;
                ret[0] = i;
                ret[1] = j;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return ret;
}

 确实是把题目做出来了，但是没想到吧，后面题目还有进阶提升：可以想出一个时间复杂度小于 O(n2) 的算法吗？

这种情况禁止使用两次for循环了，又有什么好方法解决？很多人就会想，做出来就行了，不需要想进阶的思路，但是进阶的思路应该是第一次刷题的人很久也想不出来的思路,因为用到了哈希表，真的是想不到的思路，当时本人想了好久也没有想出来，因为真的学了之后就没用过哈希表。

使用哈希表之前需要定义哈希表的结构体，然后定义一个哈希表指针：

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

struct hashTable* hashtable;

编写哈希表相关功能的函数，在双数之和这道题目里，需要定义查找和插入两个函数：

查找函数：当我们在哈希表中，如果查询哈希表中存在【target(目标值) -数组某元素】的值，利用HASH_FIND_INT函数，返回返回NULL或对应键的结构。

HASH_FIND_INT函数：第一个参数users是哈希表；第二个参数是user_id的地址（一定要传递地址）；最后s是输出变量。当可以在哈希表中找到相应键值时，s返回给定键的结构，当找不到时s返回NULL。

插入函数：传入哈希表结构体定义的key和val，查找是否存在key对应的结构体，如果存在则修改对应的val，没有相应key的话，则初始话哈希表变量指针之后，利用 HASH_ADD_INT函数插入到哈希表中。

HASH_ADD_INT表示添加的键值为int类型

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;
    }
}

当写完相应的功能之后，就可以开始主功能的编写了，利用for循环遍历整个数组元素，利用find函数查找是否存在【target(目标值) -数组某元素】，当存在的时候返回值不为NULL，用一个int数组存放对应的数组下标，最后返回该数组就行；当不存在的时候就把该数组元素作为哈希表元素插入到哈希表中，这样做可以保证不会让数组元素与自身相加。

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;
}