LeetCode1.Two Sum

1.題目

2.題意

傳回相加的兩數等于特定值的索引

3.我的解法   

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int *a = (int*)malloc(2*sizeof(int));
    for(int i = 0;i<numsSize;i++)
    {
        for(int j = i+1;(j<numsSize && j != i);j++)
        {
            if(nums[i] + nums[j] == target)
            {
                a[0] = i;
                a[1] = j;
            }
        }
    }
    return a;
}
           

這是比較垃圾的方法，隻5.21%。

4.優秀方法

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct Node{  /*先定義一個結點，有鍵值，還有一個指向next 的指針*/
	int key;
	int value;
	struct Node* next;
}Node;

typedef struct HashSet{  /*定義hashset，首先是大小，然後設定一個指向node位址（node*）的指針table，即指向指針的指針*/
	int mapSize;
	Node** table;
}HashSet;

void initMap(HashSet* set, int mapSize){
/*初始化map，先設定大小，再給table配置設定記憶體，配置設定語句是這樣一個構造，（要配置設定的變量類型，這裡就是node**）+
malloc+（sizeof（基礎類型node*）*基礎類型的大小數量）；再用memset，這個函數是将set->table以後的sizeof(Node*) * mapSize
個位元組的内容全部替換為0*/
    set->mapSize=mapSize;
	set->table = (Node**)malloc(sizeof(Node*) * mapSize);
	memset(set->table,0,sizeof(Node*) * mapSize);
}

bool addData(HashSet* set,int key,int value){
	/*這裡的key取了具體值，value是索引下标；這裡的hash對負數取反，然後用求餘做hash值，定義一個node類型指針ptr，指向代表hash值的table位置
	這個while的作用是判斷有沒有加入重複的資料，當一個新值進來了，ptr必定指向null，也就是跳過while，執行下面的key，value指派，同時插入table[hash]對應的後面
	當一個舊值，重複值進來了，ptr一定指向一個不為空的位址，執行while，相當于處理沖突*/ 
	int hash = key > 0 ? key : -key;
	hash%=set->mapSize;
	Node *ptr = set->table[hash];

	while(ptr!=NULL){
		if(ptr->key==key){
			return false;
		}
		ptr=ptr->next;
	}
	ptr=malloc(sizeof(Node));
	ptr->key=key;
	ptr->value=value;
	ptr->next=set->table[hash];
	set->table[hash]=ptr;

	return true;
}

bool containsKey(HashSet* set, int key){
	/*這個函數主要是判斷hashtab裡面是否含有重複值，用到的是上面的while*/ 
	int hash = key>0 ? key:-key;
	hash%=set->mapSize;
	Node* ptr=set->table[hash];

	while(ptr!=NULL){
		if(ptr->key==key){
			return true;
		}
		ptr=ptr->next;
	}
	return false;
}

int getValue(HashSet* set,int key){
	/*與上面的函數功能類似，隻不過傳回的是value值或者0*/
	int hash = key>0 ? key:-key;
	hash%=set->mapSize;
	Node* ptr=set->table[hash];

	while(ptr!=NULL){
		if(ptr->key==key){
			return ptr->value;
		}
		ptr=ptr->next;
	}

	return 0;

}

int* twoSum(int* nums, int numsSize, int target) {
    HashSet map; 
    initMap(&map,numsSize);
    int* ret = (int*)malloc(sizeof(int)*2);
    for(int i=0;i<numsSize;i++){
        if(containsKey(&map,target-nums[i])){
            ret[0]=getValue(&map,target-nums[i]);
            ret[1]=i;
            return ret;
        }
        else{
            addData(&map,nums[i],i);
        }
    }
    return -1;
}
           

優于98%，使用hashtable