来源：Leetcode第一题两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
建立哈希表
常规思路是暴力求解，但是这样的时间复杂度是O(n^2)，而利用哈希表进行迭代将元素插入到表中的同时，并且回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回，这可以将时间复杂度降至O(n)，但是也占用了O(n)的空间复杂度。C语言代码如下：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
83
84
85
86
87
88
89
90
91/* hash map method */
struct hash_data{
int index;
// int data;
};
struct hash_table
{
struct hash_data* element;
const int* nums;
int count;
};
int hash_init(struct hash_table* table, int count){
if(count<=0)
return -1;
table->element = (struct hash_data*)malloc(sizeof(struct hash_data)*count);
if(table->element==NULL)
return -1;
for(int i=0; i<count; i++){
table->element[i].index = -1;
//table->element[i].data = 0;
}
table->count = count;
return 0;
}
void hash_free(struct hash_table* table){
if(table->element!=NULL){
free(table->element);
table->element = NULL;
}
table->count = 0;
}
int hash_addr(int data, int table_count){
int addr = data % table_count;
return (addr>=0)?addr:(addr+table_count);
}
void hash_insert(struct hash_table* table, int data, int index){
int addr = hash_addr(data, table->count);
while(table->element[addr].index>=0){ //解决冲突
addr = (addr+1)%table->count;
}
table->element[addr].index = index; //addr是与data有关的函数构成
//table->element[addr].data = data;
}
struct hash_data* hash_find(struct hash_table* table, int data){ //查找表
int primary;
int addr = primary = hash_addr(data, table->count);
do{
if(table->element[addr].index<0)
return NULL;
if(table->nums[table->element[addr].index] == data){
return &table->element[addr];
}
addr = (addr+1)%table->count; //插入时冲突情况
}while(addr!=primary);
return NULL;
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int * ret = NULL;
int addr;
struct hash_table table;
struct hash_data *p_data;
if(hash_init(&table, numsSize+numsSize/5)<0){ //为什么要numsSize+numsSize/5来初始化哈希表？
return twoSum_basic(nums, numsSize, target, returnSize);
};
table.nums = nums;
*returnSize = 0;
for(int i=0; i<numsSize; i++){
if ((p_data=hash_find(&table,target-nums[i]))!=NULL){
if((ret = (int*)malloc(2*sizeof(int)))==NULL){
break;
}
ret[0] = p_data->index;
ret[1] = i;
*returnSize = 2;
return ret;
}
hash_insert(&table, nums[i], i);
}
hash_free(&table);
return NULL;
}
哈希遍历
遍历数组，将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。
1 | public int[] twoSum(int[] nums, int target) { |