Two Sum (两数之和) - Hash Table (哈希表)

电玩女神 2022-10-10 14:52 112阅读 0赞

# **Two Sum (两数之和) - Hash Table (哈希表)** #

[https://leetcode-cn.com/problems/two-sum/][https_leetcode-cn.com_problems_two-sum]

Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出和为目标值 `target` 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

**Example 1:**

Input: nums = [2,7,11,15], target = 9
    Output: [0,1]
    Output: Because nums[0] + nums[1] == 9, we return [0, 1].

**Example 2:**

Input: nums = [3,2,4], target = 6
    Output: [1,2]

**Example 3:**

Input: nums = [3,3], target = 6
    Output: [0,1]

**Constraints:**

*   2 2 2 <= nums.length <=  1 0 4 10^4 104
 *   − 1 0 9 -10^9 −109 <= nums\[i\] <=  1 0 9 10^9 109 (注意包含负数)
 *   − 1 0 9 -10^9 −109 <= target <=  1 0 9 10^9 109
 *  Only one valid answer exists (只会存在一个有效答案).

Follow-up: Can you come up with an algorithm that is less than  O ( n 2 ) O(n^2) O(n2) time complexity?  
进阶：你可以想出一个时间复杂度小于  O ( n 2 ) O(n^2) O(n2) 的算法吗？

A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it’s best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

So, if we fix one of the numbers, say `x`, we have to scan the entire array to find the next number `y` which is  
`value - x`, where `value` is the input parameter.

brute force [bruːt fɔːs]：n. 暴力，强力
    Brute Force，BF：暴力算法

### (1) 暴力枚举 ###

枚举数组中的每一个数 `x`，寻找数组中是否存在 `target - x`。

当我们使用遍历整个数组的方式寻找 `target - x` 时，需要注意到每一个位于 `x` 之前的元素都已经和 `x` 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 `x` 后面的元素中寻找 `target - x`。

时间复杂度： O ( N 2 ) O(N^2) O(N2)，其中 `N` 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

### (2) 哈希表 ###

哈希表使用空间来换取时间，将查找时间从  O ( n ) O(n) O(n) 降低为  O ( 1 ) O(1) O(1)。 哈希表支持以近似恒定的时间进行快速查找。一旦出现冲突 (Collision)，查找用时可能会退化到  O ( n ) O(n) O(n)。仔细的挑选哈希函数，在哈希表中进行查找的用时应当被摊销为  O ( 1 ) O(1) O(1)。

使用哈希表，可以将寻找 `target - x` 的时间复杂度降低到从  O ( N ) O(N) O(N) 降低到  O ( 1 ) O(1) O(1)。

创建一个哈希表，对于每一个 `x`，我们首先查询哈希表中是否存在 `target - x`，然后将 `x` 插入到哈希表中，即可保证不会让 `x` 和自己匹配。

创建 hash table 特别注意 `x` 有可能为负数，可以将所有 `x` 加上一个值变成正数，然后再计算 hash idx。

时间复杂度：`O(N)`，其中 `N` 是数组中的元素数量。对于每一个元素 `x`，我们可以 `O(1)` 地寻找 `target - x`。

## 1. solution 1 - 两遍哈希表 ##

哈希表的实现方式：链地址法

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #define MAX_HASH_LEN (13331)
    #define MAX_ARRAY_LEN (10000 + 4)
    
    #define MAX_NUM (1000000000 + 2)
    
    typedef struct NODE {
    	struct NODE *prev;
    	struct NODE *next;
    	int num;
    	int arr_idx;
    } Node;
    
    Node hash_table[MAX_HASH_LEN];  // init()
    
    Node node_pool[MAX_ARRAY_LEN];
    int node_pool_idx = 0;  // init()
    
    void init()
    {
    	node_pool_idx = 0;
    
    	// hash table - 头节点
    	for (int i = 0; i < MAX_HASH_LEN; ++i) {
    		(hash_table[i]).prev = (hash_table[i]).next = &(hash_table[i]);
    	}
    }
    
    // 带头节点的双向链表 - 插入函数
    void insert_node(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    	node->next->prev = node;
    	head->next = node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node_src(Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node(Node *node)
    {
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    int hash_code(const int num)
    {
    	// hash_idx >= 0
    	const int hash_idx = (num + MAX_NUM) % MAX_HASH_LEN;
    	return hash_idx;
    }
    
    /**
    * Note: The returned array must be malloced, assume caller calls free().
    */
    int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    
    	int *ret_idxs = NULL;
    	*returnSize = 0;
    
    	// init
    	init();
    
    	// insert
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num = nums[i];
    		const int hash_idx = hash_code(num);
    
    		Node *head = &(hash_table[hash_idx]);
    		Node *node = &(node_pool[node_pool_idx++]);
    		node->num = num;
    		node->arr_idx = i;
    
    		insert_node(head, node);
    	}
    
    	// search
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num1 = nums[i];
    		const int num1_idx = i;
    
    		const int num2 = target - num1;
    		const int hash_idx = hash_code(num2);
    
    		Node *head = &(hash_table[hash_idx]);
    		Node *ptr_node = head->next;
    
    		int find_flag = 0;
    		while (ptr_node != head)
    		{
    			if ((num2 == ptr_node->num) && (num1_idx != ptr_node->arr_idx)) {
    				find_flag = 1;
    				break;
    			}
    
    			ptr_node = ptr_node->next;
    		}
    
    		if (1 == find_flag)
    		{
    			*returnSize = 2;
    			ret_idxs = (int *)malloc(2 * sizeof(int));
    			ret_idxs[0] = i;
    			ret_idxs[1] = ptr_node->arr_idx;
    			break;
    		}
    	}
    
    	return ret_idxs;
    }

![在这里插入图片描述][20210629000603678.png_pic_center]

## 2. solution 2 - 一遍哈希表 ##

哈希表的实现方式：链地址法

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #define MAX_HASH_LEN (13331)
    #define MAX_ARRAY_LEN (10000 + 4)
    
    #define MAX_NUM (1000000000 + 2)
    
    typedef struct NODE {
    	struct NODE *prev;
    	struct NODE *next;
    	int num;
    	int arr_idx;
    } Node;
    
    Node hash_table[MAX_HASH_LEN];  // init()
    
    Node node_pool[MAX_ARRAY_LEN];
    int node_pool_idx = 0;  // init()
    
    void init()
    {
    	node_pool_idx = 0;
    
    	// hash table - 头节点
    	for (int i = 0; i < MAX_HASH_LEN; ++i) {
    		(hash_table[i]).prev = (hash_table[i]).next = &(hash_table[i]);
    	}
    }
    
    // 带头节点的双向链表 - 插入函数
    void insert_node(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    	node->next->prev = node;
    	head->next = node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node_src(Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    // 带头节点的双向链表 - 删除函数
    void delete_node(Node *node)
    {
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    int hash_code(const int num)
    {
    	// hash_idx >= 0
    	const int hash_idx = (num + MAX_NUM) % MAX_HASH_LEN;
    	return hash_idx;
    }
    
    /**
    * Note: The returned array must be malloced, assume caller calls free().
    */
    int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    
    	int *ret_idxs = NULL;
    	*returnSize = 0;
    
    	// init
    	init();
    
    	// search and insert
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num1 = nums[i];
    		const int num1_idx = i;
    
    		const int num2 = target - num1;
    		const int hash_idx = hash_code(num2);
    
    		Node *head = &(hash_table[hash_idx]);
    		Node *ptr_node = head->next;
    
    		int find_flag = 0;
    		while (ptr_node != head)
    		{
    			if (num2 == ptr_node->num) {
    				find_flag = 1;
    				break;
    			}
    
    			ptr_node = ptr_node->next;
    		}
    
    		if (1 == find_flag)
    		{
    			*returnSize = 2;
    			ret_idxs = (int *)malloc(2 * sizeof(int));
    			ret_idxs[0] = i;
    			ret_idxs[1] = ptr_node->arr_idx;
    			break;
    		}
    		else {
    			const int hash_idx = hash_code(num1);
    
    			Node *head = &(hash_table[hash_idx]);
    			Node *node = &(node_pool[node_pool_idx++]);
    			node->num = num1;
    			node->arr_idx = i;
    
    			insert_node(head, node);
    		}
    	}
    
    	return ret_idxs;
    }

![在这里插入图片描述][20210629153836935.png_pic_center]

## 3. solution 3 - 两遍哈希表 ##

哈希表的实现方式：线性探测法

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #define MAX_HASH_LEN (23333)
    #define MAX_ARRAY_LEN (10000 + 4)
    
    #define MAX_NUM (1000000000 + 2)
    
    typedef struct NODE {
    	int yes;  // default = 0
    	int num;
    	int arr_idx;
    	int idx;
    } Node;
    
    Node node_array[MAX_HASH_LEN];  // init()
    
    void init()
    {
    	// hash table - 头节点
    	for (int i = 0; i < MAX_HASH_LEN; ++i) {
    		(node_array[i]).yes = 0;
    	}
    }
    
    int hash_code_linear(const int num, const int idx)
    {
    	// arr_idx >= 0
    	int arr_idx = (num + MAX_NUM) % MAX_HASH_LEN;
    
    	while (1)
    	{
    		// yes = 0
    		if (0 == (node_array[arr_idx]).yes)
    		{
    			(node_array[arr_idx]).yes = 1;
    			(node_array[arr_idx]).num = num;
    			(node_array[arr_idx]).arr_idx = arr_idx;
    			(node_array[arr_idx]).idx = idx;
    			break;
    		}
    
    		// yes = 1
    		if ((num == (node_array[arr_idx]).num) && (idx == (node_array[arr_idx]).idx)) {
    			break;
    		}
    
    		arr_idx += 1;
    		if (arr_idx >= MAX_HASH_LEN) {
    			arr_idx = 0;
    		}
    	}
    
    	return arr_idx;
    }
    
    int hash_code_linear_search(const int num, const int idx)
    {
    	// arr_idx >= 0
    	int arr_idx = (num + MAX_NUM) % MAX_HASH_LEN;
    
    	while (1)
    	{
    		// yes = 0
    		if (0 == (node_array[arr_idx]).yes)
    		{
    			return -1;
    		}
    
    		// yes = 1
    		if ((num == (node_array[arr_idx]).num) && (idx != (node_array[arr_idx]).idx)) {
    			break;
    		}
    
    		arr_idx += 1;
    		if (arr_idx >= MAX_HASH_LEN) {
    			arr_idx = 0;
    		}
    	}
    
    	return arr_idx;
    }
    
    /**
    * Note: The returned array must be malloced, assume caller calls free().
    */
    int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    
    	int *ret_idxs = NULL;
    	*returnSize = 0;
    
    	// init
    	init();
    
    	// insert
    	for (int i = 0; i < numsSize; ++i) {
    		const int arr_idx = hash_code_linear(nums[i], i);
    	}
    
    	// search
    	for (int i = 0; i < numsSize; ++i)
    	{
    		const int num1 = nums[i];
    		const int num1_idx = i;
    
    		const int num2 = target - num1;
    		const int num2_arr_idx = hash_code_linear_search(num2, i);
    
    		if (-1 != num2_arr_idx)
    		{
    			*returnSize = 2;
    			ret_idxs = (int *)malloc(2 * sizeof(int));
    			ret_idxs[0] = i;
    			ret_idxs[1] = (node_array[num2_arr_idx]).idx;
    			break;
    		}
    	}
    
    	return ret_idxs;
    }

![在这里插入图片描述][20210630001901823.png_pic_center]

## References ##

[https://leetcode-cn.com/problems/two-sum/][https_leetcode-cn.com_problems_two-sum]

[https_leetcode-cn.com_problems_two-sum]: https://leetcode-cn.com/problems/two-sum/
[20210629000603678.png_pic_center]: /images/20221005/05d2bca2936b470d9b1b5cb35a50b27f.png
[20210629153836935.png_pic_center]: /images/20221005/0a76e8ac757e43398866fc4ac85e5757.png
[20210630001901823.png_pic_center]: /images/20221005/d5a34496784a42d0b5cb16b64ebc4bc8.png