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/problems/two-sum
解题：
//
//
#include <stdio.h>
#include <stdlib.h>
static int mapSize = 8;
static int halfMapSize;
typedef struct node{
int key;
int value;
struct node* next;
}NODE;
static NODE** map;
/**
* 初始化map
* @param size
*/
static void initMap(int size){
for(int i = 1;; i++){
if(mapSize >= size){
break;
}
mapSize = mapSize << 1;
}
halfMapSize = mapSize / 2;
map = (NODE**)malloc(mapSize * sizeof(NODE*));
for(int i = 0; i < mapSize; i++){
map[i] = NULL;
}
}
/**
* 根据key获取下标
* @param key
* @return
*/
static int getIndex(int key){
if(key < 0){
key = -key;
return key & (halfMapSize - 1);
}
int index = halfMapSize + (key & (halfMapSize - 1));
return index;
}
/**
* 放入到map中
* @param key
* @param value
*/
static void putToMap(int key, int value){
int index = getIndex(key);
// 创建节点
NODE * node = (NODE*)malloc(sizeof(NODE));
node->key = key;
node->value = value;
node->next = NULL;
if(map[index] == NULL){
map[index] = node;
return;
}
NODE * targetNode = map[index];
while (targetNode->next){
targetNode = targetNode->next;
}
// 挂在最后一个节点上
targetNode->next = node;
}
/**
* 根据key查找
* @param key
* @return
*/
static NODE* get(int key){
// 定位
int index = getIndex(key);
NODE * node = map[index];
while (node){
if(node->key == key){
return node;
}
node = node->next;
}
return node;
}
static void showMap(){
NODE * node;
for(int i = 0; i < mapSize; i++){
node = map[i];
while (node){
printf("%d-%d ", node->key, node->value);
node = node->next;
}
printf("\n");
}
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
initMap(numsSize);
int i, j;
NODE * node;
*returnSize = 0;
int * result = (int*)malloc(sizeof(int) * 2);
for(i = 0; i < numsSize; i++) {
j = target - nums[i];
node = get(j);
if(node != NULL){
*returnSize = 2;
result[0] = node->value;
result[1] = i;
return result;
}else {
putToMap(nums[i], i);
}
};
free(result);
return NULL;
}
int main(){
int arr[100] = {
230,863,916,585,981,404,316,785,88 ,12 ,70 ,435,384,778,887,755,740,337, 86,92,
325,422,815,650,920,125,277,336,221,847,168,23 ,677,61 ,400,136,874,363,394,199,
863,997,794,587,124,321,212,957,764,173,314,422,927,783,930,282,306,506, 44,926,
691,568,68 ,730,933,737,531,180,414,751,28 ,546,60 ,371,493,370,527,387, 43,541,
13 ,457,328,227,652,365,430,803,59 ,858,538,427,583,368,375,173,809,896,370,789};
int returnSize;
int *result = twoSum(arr, 100, 542, &returnSize);
for(int i = 0; i < returnSize; i++){
printf("%d ", result[i]);
}
return 0;
}