leetcode-1. 两数之和

leetcode-1. 两数之和。

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

  给定 nums = [2, 7, 11, 15], target = 9，
  因为 nums[0] + nums[1] = 2 + 7 = 9，
  所以返回 [0, 1]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problemset/all/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：暴力循环。

int *twoSum( int *nums, int numsSize, int target, int *returnSize ) {
	int *answer = NULL;

	returnSize[0] = 0;
	answer = malloc( sizeof(*answer) * 2 );
	for( int i = 0; i < numsSize; ++i ) {
		for( int j = i + 1; j < numsSize; ++j ) {
			if( target - nums[i] == nums[j] ) {
				answer[returnSize[0]++] = i;
				answer[returnSize[0]++] = j;
				break;
			}
		}
	}

	return answer;
}

解法二：使用HashTable 或 HashMap，二次遍历过程。

// 封装 uthash 开始.
#define ERROR_EXIT( expression ) 
if( (expression) ) exit( EXIT_FAILURE )

typedef void ( TraversalHashTableFunc )( int key, int value );

typedef struct NodeHashTable {
	int k;
	int v;
	UT_hash_handle hh;
} NodeHashTable, HashTable;

// 功能: 创建一个新的哈希表.
// 参数: 无.
// 返回: NULL.
// 注意: uthash里的新表应该初始为NULL.
HashTable *newHashTable( void ) {
	return NULL;
}

// 功能: 将键值对加入到哈希表中.
// 参数: ht(存放哈希表对象的指针的指针), key(键), value(值).
// 返回: 无.
// 注意: 当 ht 为NULL 时, 将错误退出程序, 当键存在时,则更新键值为value.
void putHashTable( HashTable **ht, int key, int value ) {
	NodeHashTable *n = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_FIND_INT( *ht, &key, n );
	if( n == NULL ) {
		n = malloc( sizeof(*n) );
		n->k = key;
		HASH_ADD_INT( *ht, k, n );
	}
	n->v = value;
}

// 功能: 将键值对从哈希表中移除.
// 参数: ht(存放哈希表对象的指针的指针), key(键).
// 返回: 被移除的键值.
// 注意: 当 ht 为NULL 或 键不存在 时, 将错误退出程序.
int removeHashTable( HashTable **ht, int key ) {
	int value = 0;
	NodeHashTable *n = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_FIND_INT( *ht, &key, n );
	ERROR_EXIT( n == NULL );
	HASH_DEL( *ht, n );
	value = n->v;
	free( n );

	return value;
}

// 功能: 哈希表中是否包含了指定键.
// 参数: ht(哈希表对象的指针), key(键).
// 返回: 表中包含了指定键返回1, 否则返回0.
// 注意: 无.
int existHashTable( HashTable *ht, int key ) {
	NodeHashTable *n = NULL;

	HASH_FIND_INT( ht, &key, n );

	return n != NULL;
}

// 功能: 将键值对从哈希表中移除.
// 参数: ht(哈希表对象的指针), key(键).
// 返回: 键对应的键值.
// 注意: 当 键不存在 时, 将错误退出程序.
int getHashTable( HashTable *ht, int key ) {
	NodeHashTable *n = NULL;

	HASH_FIND_INT( ht, &key, n );
	ERROR_EXIT( n == NULL );

	return n->v;
}

// 功能: 得到哈希表实际已使用大小.
// 参数: ht(哈希表对象的指针).
// 返回: 哈希表实际已使用大小.
// 注意: 无.
int sizeHashTable( HashTable *ht ) {
	return HASH_COUNT( ht );
}

// 功能: 判断是否为空哈希表.
// 参数: ht(哈希表对象的指针).
// 返回: 是空表返回1, 否则返回0.
// 注意: 无.
int emptyHashTable( HashTable *ht ) {
	return HASH_COUNT( ht ) < 1;
}

// 功能: 判断是否为满哈希表.
// 参数: ht(哈希表对象的指针).
// 返回: 0.
// 注意: uthash实现为链式存储,理论上容量是无限制的.
int fullHashTable( HashTable *ht ) {
	return 0;
}

// 功能: 遍历哈希表.
// 参数: ht(哈希表对象的指针), func(用户自定义函数的指针).
// 返回: 无.
// 注意: 当 func 为NULL 时, 将错误退出程序, 在迭代遍历过程中每次都把键值对传给func.
void traversalHashTable( HashTable *ht, TraversalHashTableFunc *func ) {
	ERROR_EXIT( func == NULL );
	for( NodeHashTable *n = ht; n != NULL; n = n->hh.next ) {
		func( n->k, n->v );
	}
}

// 功能: 清空哈希表.
// 参数: ht(存放哈希表对象的指针的指针), func(用户自定义函数的指针).
// 返回: 无.
// 注意: 当 ht 为NULL 时, 将错误退出程序, 当 func 不为 NULL 时,在移除每对键值对之前把键值对传给func.
void clearHashTable( HashTable **ht, TraversalHashTableFunc *func ) {
	NodeHashTable *c = NULL, *t = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_ITER( hh, *ht, c, t ) {
		HASH_DEL( *ht, c );
		if( func ) {
			func( c->k, c->v );
		}
		free( c );
	}
}

// 功能: 销毁哈希表.
// 参数: ht(存放哈希表对象的指针的指针), func(用户自定义函数的指针).
// 返回: 无.
// 注意: 当 ht 为NULL 时, 将错误退出程序, 当 func 不为 NULL 时,在移除每对键值对之前把键值对传给func.
void delHashTable( HashTable **ht, TraversalHashTableFunc *func ) {
	NodeHashTable *c = NULL, *t = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_ITER( hh, *ht, c, t ) {
		HASH_DEL( *ht, c );
		if( func ) {
			func( c->k, c->v );
		}
		free( c );
	}
}
// 封装 uthash 结束.

int *twoSum( int *nums, int numsSize, int target, int *returnSize ) {
	int *answer = NULL;
	HashTable *ht = newHashTable();

	returnSize[0] = 0;
	answer = malloc( sizeof(*answer) * 2 );
	for( int i = 0; i < numsSize; ++i ) {
		putHashTable( &ht, nums[i], i );
	}
	for( int i = 0; i < numsSize; ++i ) {
		int j = target - nums[i];
		if( existHashTable( ht, j ) && getHashTable( ht, j ) != i ) {
			answer[returnSize[0]++] = i;
			answer[returnSize[0]++] = getHashTable( ht, j );
			break;
		}
	}
	delHashTable( &ht, NULL );

	return answer;
}

解法三：使用HashTable 或 HashMap，一次遍历过程。

// 封装 uthash 开始.
#define ERROR_EXIT( expression ) 
if( (expression) ) exit( EXIT_FAILURE )

typedef void ( TraversalHashTableFunc )( int key, int value );

typedef struct NodeHashTable {
	int k;
	int v;
	UT_hash_handle hh;
} NodeHashTable, HashTable;

// 功能: 创建一个新的哈希表.
// 参数: 无.
// 返回: NULL.
// 注意: uthash里的新表应该初始为NULL.
HashTable *newHashTable( void ) {
	return NULL;
}

// 功能: 将键值对加入到哈希表中.
// 参数: ht(存放哈希表对象的指针的指针), key(键), value(值).
// 返回: 无.
// 注意: 当 ht 为NULL 时, 将错误退出程序, 当键存在时,则更新键值为value.
void putHashTable( HashTable **ht, int key, int value ) {
	NodeHashTable *n = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_FIND_INT( *ht, &key, n );
	if( n == NULL ) {
		n = malloc( sizeof(*n) );
		n->k = key;
		HASH_ADD_INT( *ht, k, n );
	}
	n->v = value;
}

// 功能: 将键值对从哈希表中移除.
// 参数: ht(存放哈希表对象的指针的指针), key(键).
// 返回: 被移除的键值.
// 注意: 当 ht 为NULL 或 键不存在 时, 将错误退出程序.
int removeHashTable( HashTable **ht, int key ) {
	int value = 0;
	NodeHashTable *n = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_FIND_INT( *ht, &key, n );
	ERROR_EXIT( n == NULL );
	HASH_DEL( *ht, n );
	value = n->v;
	free( n );

	return value;
}

// 功能: 哈希表中是否包含了指定键.
// 参数: ht(哈希表对象的指针), key(键).
// 返回: 表中包含了指定键返回1, 否则返回0.
// 注意: 无.
int existHashTable( HashTable *ht, int key ) {
	NodeHashTable *n = NULL;

	HASH_FIND_INT( ht, &key, n );

	return n != NULL;
}

// 功能: 将键值对从哈希表中移除.
// 参数: ht(哈希表对象的指针), key(键).
// 返回: 键对应的键值.
// 注意: 当 键不存在 时, 将错误退出程序.
int getHashTable( HashTable *ht, int key ) {
	NodeHashTable *n = NULL;

	HASH_FIND_INT( ht, &key, n );
	ERROR_EXIT( n == NULL );

	return n->v;
}

// 功能: 得到哈希表实际已使用大小.
// 参数: ht(哈希表对象的指针).
// 返回: 哈希表实际已使用大小.
// 注意: 无.
int sizeHashTable( HashTable *ht ) {
	return HASH_COUNT( ht );
}

// 功能: 判断是否为空哈希表.
// 参数: ht(哈希表对象的指针).
// 返回: 是空表返回1, 否则返回0.
// 注意: 无.
int emptyHashTable( HashTable *ht ) {
	return HASH_COUNT( ht ) < 1;
}

// 功能: 判断是否为满哈希表.
// 参数: ht(哈希表对象的指针).
// 返回: 0.
// 注意: uthash实现为链式存储,理论上容量是无限制的.
int fullHashTable( HashTable *ht ) {
	return 0;
}

// 功能: 遍历哈希表.
// 参数: ht(哈希表对象的指针), func(用户自定义函数的指针).
// 返回: 无.
// 注意: 当 func 为NULL 时, 将错误退出程序, 在迭代遍历过程中每次都把键值对传给func.
void traversalHashTable( HashTable *ht, TraversalHashTableFunc *func ) {
	ERROR_EXIT( func == NULL );
	for( NodeHashTable *n = ht; n != NULL; n = n->hh.next ) {
		func( n->k, n->v );
	}
}

// 功能: 清空哈希表.
// 参数: ht(存放哈希表对象的指针的指针), func(用户自定义函数的指针).
// 返回: 无.
// 注意: 当 ht 为NULL 时, 将错误退出程序, 当 func 不为 NULL 时,在移除每对键值对之前把键值对传给func.
void clearHashTable( HashTable **ht, TraversalHashTableFunc *func ) {
	NodeHashTable *c = NULL, *t = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_ITER( hh, *ht, c, t ) {
		HASH_DEL( *ht, c );
		if( func ) {
			func( c->k, c->v );
		}
		free( c );
	}
}

// 功能: 销毁哈希表.
// 参数: ht(存放哈希表对象的指针的指针), func(用户自定义函数的指针).
// 返回: 无.
// 注意: 当 ht 为NULL 时, 将错误退出程序, 当 func 不为 NULL 时,在移除每对键值对之前把键值对传给func.
void delHashTable( HashTable **ht, TraversalHashTableFunc *func ) {
	NodeHashTable *c = NULL, *t = NULL;

	ERROR_EXIT( ht == NULL );
	HASH_ITER( hh, *ht, c, t ) {
		HASH_DEL( *ht, c );
		if( func ) {
			func( c->k, c->v );
		}
		free( c );
	}
}
// 封装 uthash 结束.

int *twoSum( int *nums, int numsSize, int target, int *returnSize ) {
	int *answer = NULL;
	HashTable *ht = newHashTable();

	returnSize[0] = 0;
	answer = malloc( sizeof(*answer) * 2 );
	for( int i = 0; i < numsSize; ++i ) {
		if( existHashTable( ht, target - nums[i] ) ) {
			answer[returnSize[0]++] = getHashTable( ht, target - nums[i] );
			answer[returnSize[0]++] = i;
			break;
		}
		putHashTable( &ht, nums[i], i );
	}
	delHashTable( &ht, NULL );

	return answer;
}