题目描述:
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
1
2
3给定 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]的两个数组下标;
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/** * 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语言版内容请搜索靠谱客的其他文章。
发表评论 取消回复