Leet_code---1两数之和---C语言版

题目描述：

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题干分析：

  本题没有任何干扰项，每种输入答案唯一，最简单的思路便是直接双层循环，直至求出两数相加等于target即可;

解题思路：

  最简单的思路运算起来时O(n²)，省了脑空间的同时效率很低，所以在这里我们选用哈希表来实现本题的快速解题。步骤如下：

    ①由题干可知target为两数相加，哈希表的最大长度==target-nums[min];

    ②将值映射进入哈希表，选用 table[nums[i]-min] = i这一公式进行赋值，方便后续计算;

    ③在赋值的同时进行冲突判定：table[target-nums[i]-min] != -1//地址是否有存储值;

冲突判定起关键作用，换成数学等式即为 target-nums[a]-min==nums[b]-min;

公式简单移项后为：target==nums[a]+nums[b]，ab即为我们要求的值;

a=i;b=table[target-nums[i]-min],用哈希表内的值确定b;

   哈希表的存储和冲突判定采用了不同的规则，实际上如果冲突判定规则相同：

            (即table[nums[i]-min] ！= -1)，此时会返回相同值对应的数组下标。

  按这个思路把target换成其他对应公式，都可以得到符合此公式的两个数组下标值，只是需要修改映射时的对应规则;

  例如：映射规则tabel[2*nums[i]]=i;

            冲突判定：table[nums[i]] != -1; 此时便是寻找nums中nums[a]=2*nums[b]的两个数组下标;

代码如下

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target) {
int min = INT_MAX;
int i = 0;
for (i = 0; i < numsSize; i++) {
if (nums[i] < min)
min = nums[i];
}
//寻找最小值
int max = target - min;
int len = max - min + 1;
//确定hash的最大长度,实际需要的长度可能小于此
int *table = (int*)malloc(len*sizeof(int));
int *indice = (int*)malloc(2*sizeof(int));
for (i = 0; i < len; i++) {
table[i] = -1;
//hash初值
}
for (i = 0; i < numsSize; i++) {
if (nums[i]-min < len) {
if (table[target-nums[i]-min] != -1) {
//满足相加为target，此部分为代码核心,可借此理解哈希表
indice[0] = table[target-nums[i] - min];
indice[1] = i;
return indice;
}
table[nums[i]-min] = i;
}
}
free(table);//在实际操作中勿忘free
return indice;
}

  哈希表的应用对这道题可能存在的弊端是占用空间过大,哈希表的存取都是O(1)操作，寻找最小值的操作为O(n),固总的来讲本算法时间复杂度应该是O(n);

  也可以采用最大值来确定哈希表的最大长度，感觉已经理解此算法的同学可以尝试一下;

  每天会更新部分Leet_code相关的题目，欢迎关注，谢谢。

最后

以上就是个性纸鹤为你收集整理的Leet_code---1两数之和---C语言版的全部内容，希望文章能够帮你解决Leet_code---1两数之和---C语言版所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。