Leetcode Two Sum使用Hash表来解决问题

问题描述：

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

一般来说，直接双重循环就可以解决此问题

int* twoSum(int* nums, int numsSize, int target) {
    int* ret = (char*)malloc(2 * sizeof(int));
    for (ret[0]=0; ret[0]<numsSize; ret[0]++) {
        for (ret[1]=ret[0]+1; ret[1]<numsSize; ret[1]++) {
            if (nums[ret[0]] + nums[ret[1]] == target) {
                return ret;
            } 
        }
    }
    return ret;
}

可是这样太慢了，足足用了132ms

我们可以看到程序主要进行查询操作，如果我们能利用Hash表进行查询操作，那么就会快很多

什么是Hash表？¹
在计算机中，哈希表是一种实现关联数组抽象数据类型的数据结构，该结构可以将键映射到值。Hash表使用Hash函数来计算索引，从中找到所需要的值
选择一个Hash函数²
一般来说对于整数值可以直接进行取余操作

int Hash_Function(int key, Hash H) {
	return abs(key) % H->size;
}

解决Hash冲突²
假设选择的Hash函数为Hash(X) = X mod 10，那么很显然1，11，21，31会映射到同一个索引index =1，这时候可以构造一个链表把它们连接起来

如何利用Hash表来解决本题？
已经发现此题慢在查询操作，因此构建Hash表能够极大的增加查询速度

选择合适的Key，以及Value
在本题中key = nums[i], value = i
选择Hash函数以及解决Hash冲突

完整代码

#define HashSize 911

typedef struct HashNode Node;
struct HashNode {
    int key;
    int val;
    Node* next;
};

typedef struct HashTable Hash;
struct HashTable {
    int size;
    Node* lists;
};

void Hash_Init(Hash* H);
int Hash_Find(Hash* H, int key);
void Hash_Insert(Hash* H, int key, int val);
int Hash_Function(int key, Hash* H);

int* twoSum(int* nums, int numsSize, int target) {
    Hash H;
    Hash_Init(&H);
    for (int i=0; i<numsSize; i++) {
    	/*
    	查询操作
    	*/
        int index = Hash_Find(&H, target-nums[i]);
        if (index != -1) {
            int* result = (int *)malloc(sizeof(int) * 2);
            result[0] = index;
            result[1] = i;
            return result;
        }
        Hash_Insert(&H, nums[i], i);
    }
    return NULL;
}

int Hash_Function(int key, Hash* H) {
    return abs(key) % H->size;
}

void Hash_Init(Hash* H) {
    H->size = HashSize;
    H->lists = (Node *)malloc(sizeof(Node) * H->size);
    for (int i=0; i<H->size; i++)
        H->lists[i].next = NULL;
}

int Hash_Find(Hash* H, int key) {
    Node* pointer = H->lists + Hash_Function(key, H);
    while (pointer->next != NULL) {
        pointer = pointer->next;
        if (pointer->key == key)
            return pointer->val;
    }
    return -1;
}

void Hash_Insert(Hash* H, int key, int val) {
	/*
	该pointer指针指向拥有相同索引的链表头
	*/
    Node* pointer = H->lists + Hash_Function(key, H);
    Node* new_node = (Node *)malloc(sizeof(Node));
    new_node->key = key;
    new_node->val = val;
    new_node->next = pointer->next;
    pointer->next = new_node;
}

这时候运行速度可以达到4ms，提升了约30倍的性能

参考文献：

节选自 WIKI Hash Table ↩︎
参考《数据结构与算法分析》第五章——散列 ↩︎ ↩︎

Leetcode Two Sum使用Hash表来解决问题

相关推荐