LeetCode第一题-C语言实现

算法

写了两个版本，一个数组一个哈希表。哈希表确实效率高，时间空间都是，不过空间上还是做的不够好，应该是我设计的问题，数组表可能没有链表好吧。

结果：

1_两数之和

要求

给一个数组和一个target，要求返回数组的两个下标，使得两下标对应的数之和为target

思路

简单算法：
  • 直接两个指针，进行移动查找。
    • 时间复杂度是 n(n-1)=>n^2
  • 先顺序排序，然后设置两个指针依次比大小，从最小的两个数之和开始，然后依次右移
    • 如果刚开始小了右移之后大了，说明没有这样的解。不不不，顺序查找可以二分法。
    • 如果到最后都一直小，说明没有这样的解
    • 时间复杂度是：刚开始的顺序排序–一般都是n^2 + 查找–一般 n^2

算法实现

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
/**  
  * Note: The returned array must be malloced, assume caller calls free().  
  **/  
 int\* twoSum(int\* nums, int numsSize, int target, int\* returnSize){  
   \*returnSize = 2;  
   int\* result = (int\*)malloc(2\*sizeof(int));  
   int m,n;  
   for(m=0;m<numsSize-1;m++){  
     for(n=m+1;n<=numsSize-1;n++){  
       if(nums\[m\]+nums\[n\]==target){  
         result\[0\]=m;  
         result\[1\]=n;  
         return result;  
      }  
    }  
  }  
   free(result);  
   return 0;  
 }  
 /**int main(){  
     int nums\[\] = {2, 7, 11,15};  
     int target = 9;  
     int numsSize = sizeof(nums) / sizeof(nums\[0\]);  
     int returnSize = 2;  
     int * result = twoSum(nums, numsSize, target, &returnSize);  
 
     printf("%d,%d",result\[0\],result\[1\]);  
     free(result);  
     return 0;  
 }**/

补充-HashMap

哈希函数的写法有很多中，我们来看看「HashMap」中的哈希函数[java]     

1
2
3
4
static final int hash(Object key) {    
	int h;  
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
    }

「HashMap」中利用了「hashCode」来完成这个转换。哈希函数不管怎么实现，都应该满足下面三个基本条件：

  • 散列函数计算得到的散列值是一个非负整数
  • 如果 key1 = key2，那 hash(key1) == hash(key2)
  • 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)

第一点：因为数组的下标是从0开始，所以哈希函数生成的哈希值也应该是非负数

第二点：同一个key生成的哈希值应该是一样的，因为我们需要通过key查找哈希表中的数据

第三点：看起来非常合理，但是两个不一样的值通过哈希函数之后可能才生相同的值，因为我们把巨大的空间转出成较小的数组空间时，不能保证每个数字都映射到数组空白处。所以这里就会才生冲突，在哈希表中我们称之为哈希冲突。我们常用解决哈希冲突的方法有两种「开放地址法」和「链表法」

总的来说hashmap就是可以实现一次查找，对于这道题，我们借助hashmap就可以实现在线性时间内找到答案。

思路

遍历数组时，我们可以检查目标值与当前数字的差是否已经在哈希表中存在，如果存在，说明我们已经找到了两个数的和等于目标值。

这样，我们只需要最多把所有num遍历一遍，就可以出结果。

流程
  • 需要把数字的值和下标都存到hash表中
  • 然后从第一个开始找，找到了就返回该数字下标和那个差的下标

上面的还是不太好，下面是网上图解

实现
​ ​
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
include <stdio.h>  

include <stdlib.h>  

define HashSize 20000  

 typedef struct {  
     int key;  
     int value;  
     int used;  
 } HashEntry;  
 ​  
 typedef struct {  
     HashEntry\* data;  
     int size;    //hashbiao长度  
 } HashMap;  
 HashMap\* createHashMap(int size) {  
     HashMap\* map = (HashMap\*)malloc(sizeof(HashMap));  
     map->data = (HashEntry\*)calloc(size, sizeof(HashEntry));  
     map->size = size;  
     //for (int i = 0; i < size; i++) {  
     //   map->data\[i\].used = 0; // 初始化为未使用  
     //}  
     return map;  
 }  
 void insert(HashMap\* map, int key, int value) {  
     int hash = abs(value) % map->size;  
     while (map->data\[hash\].used map->data\[hash\].value != 0) {  
         hash = abs(hash + 1) % map->size;  
    }  
     map->data\[hash\].key = key;  
     map->data\[hash\].value = value;  
     map->data\[hash\].used = 1; // 标记为已使用  
 }  
 int\* twoSum(int\* nums, int numsSize, int target, int\* returnSize) {  

     HashMap\* map = createHashMap(HashSize);  
 ​  
     int\* result = (int\*)malloc(2 \* sizeof(int));  
     \*returnSize = 2;  
     int i;  
     int hash;  
     for (i = 0; i < numsSize; i++) {  
         int complement = target - nums\[i\];  

         hash = abs(complement) % HashSize;  
 ​  
         if (map->data\[hash\].used map->data\[hash\].value != 0) {  
             while (map->data\[hash\].value != complement) {  

                 hash = (hash + 1) % HashSize;  
                 if ((map->data\[hash\].used ==0) && (map->data\[hash\].value == 0)) {  
                     insert(map, i, nums\[i\]);  
                     break;  // 插入后跳出循环  
                }  
                 if (map->data\[hash\].value == complement) {  
                     result\[0\] = i;  
                     result\[1\] = map->data\[hash\].key;  
                     free(map->data);  
                     free(map);  
                     return result;  
                }  
            }  
             if (map->data\[hash\].value == complement) {  
                 result\[0\] = i;  
                 result\[1\] = map->data\[hash\].key;  
                 free(map->data);  
                 free(map);  
                 return result;  
            }  
        }  
         else {  
             insert(map, i, nums\[i\]);  
        }  
    }  
 ​  
     free(map->data);  
     free(map);  
     return result;  
     //free(result);  
 }

人麻了。。

注意
  • 注意hash表的判断逻辑，初始化0和赋值为0注意区分，需要一个used判断符号来判断
  • 优化的话hash表用链表，也许可以优化空间？
  • C语言写算法太鸡肋了，赶快换语言！