我是靠谱客的博主 个性纸鹤,这篇文章主要介绍Leet_code---1两数之和---C语言版,现在分享给大家,希望可以做个参考。

题目描述:


  给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

  你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

复制代码
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语言版内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(89)

评论列表共有 0 条评论

立即
投稿
返回
顶部