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

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) 哈希表

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

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

时间复杂度：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;
}

2. solution 2

References

https://leetcode-cn.com/problems/two-sum/