Leetcode 俩数之和（哈希）

一、题目描述

给定一个整数数组 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. 最直接能想到的就是暴力解法，将数组中的每一个数据俩俩匹配、计算出和，当和等于目标值时，返回俩个数据的数组下标。双for嵌套循环代码略。

2. 因为对于数组数据x寻找数据target-x的复杂度过高，可以使用哈希算法来降低其寻找复杂度。做法是根据题目数组数量及数值范围确定哈希函数及哈希表的实现方法，根据题意从数组下标0开始遍历数组，遍历到数组数据为x时，先使用key为（target-x）在哈希表中查找对应值，如果没找到，将数据x以key为（x）存放在哈希表的对应位置。若找到哈希表中value值不为Null，即配对成功，此时输入的数组中存在当前位置的x和target -x，由于我的算法没有记录target-x的数组对应下标，在输出时再遍历一次数组找出target-x对应的数组下标联合当前位置x的数组下标组成return数组。

三 代码

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define Null 0x3f3f3f3f				// 定义哈希表的初始值，即未赋值的状态。
int hash[20001];						// 数组长度最大为10000，定义哈希表长度为20000可获取较好的性能

int find_flag(int *nums, int numsSize, int x) {
   		// 找出target-x对应的数组下标
    int i = 0;
    while (i < numsSize) {
   
        if (nums[i] == x) return i;
        i++;
    }
    return -1;
}

int find(int x){
   		// 哈希算法（取余） 数组hash为哈希表，输入的x为哈希表的key，a[x]为哈希表的值
    int i = (x % 20001 + 20001) % 20001;	// 将输入的key（key就是x）值经过算法分布在0-20000之间
    while (hash[i] != Null && hash[i] != x) {
   		// 1.当哈希表中value等于Null可返回哈希表下标
        i ++ ;								// 2.当哈希表对应位置已被赋值且value值不等key发生哈希碰撞i++往哈希表后方一直寻找空位(value值为Null)(20000个位置一定可以找到)。									
        if (i == 2 * 10010) i = 0;
    }
    return i;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
   
	memset(hash, 0x3f, sizeof(hash));
	int tmp,i =0;
	
	for (i = 0; i < numsSize; i ++ ) {
   
		int x = find(target - nums[i]);		// 先找target-x是否能在hash表中找到数据。
		if (hash[x] != Null) {
   				// 能找到的话返回当前位置和target-x的位置
		    * returnSize = 2;
		    int *ret = (int *)malloc(2 * sizeof(int));
		    ret[0] = i;
		    ret[1] = find_flag(nums, numsSize, target - nums[i]);
		    return ret;
		} else if (hash[x] == Null) {
   		// 没找到则以x为hash key存入哈希表中待匹配
		    x = find(nums[i]);				// 经过hash算法找出key值对应下标
		    hash[x] = nums[i];				// 根据对应下标在hash表中赋值
		} else {
   
		    printf("hash crash, modify hash fuction\n");
		}
	}
	
	return NULL;
}

四、结果

使用C语言需要自己手动完成hash表，坏处是代码量较大，写法较多较为复杂。好处是可以根据不同的场景去调整hash算法达到更高的效率。整体思路还是使用了空间换时间的思想。使用二维数组可以将输入hash表的key对应数组下标也保存在hash表内。可以进一步利用空间来压缩时间，免去最后因为寻找target-x的下标而遍历数组。