题目描述

分析

暴力枚举

描述

对数组每个元素x，遍历寻找元素target-x。并注意到在遍历时，当前元素已与位于其之前的元素匹配过，于是只需要在其之后的元素中查找即可。

代码

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

哈希表

描述

利用哈希表查找的时间复杂度近似为O(1)可以设计时间复杂度为O(N)的算法

代码

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
struct hashList{
int id;
int val;
UT_hash_handle hh;
};
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
struct hashList *set = NULL;
int i;
for(i = 0; i < numsSize; i++){
struct hashList *tmp;
int cor = target-nums[i];
HASH_FIND_INT(set,&cor,tmp);
if(tmp == NULL){
tmp = malloc(sizeof(struct hashList));
tmp->id = nums[i];
tmp->val = i;
HASH_ADD_INT(set,id,tmp);
}
else{
int *ret = (int *)malloc(sizeof(int)*2);
ret[0] = i;
ret[1] = tmp->val;
*returnSize = 2;
return ret;
}
}
*returnSize = 0;
return NULL;
}

收获

哈希表

对于uthash的使用又更加熟练了。

最后

以上就是舒服柚子为你收集整理的leetcode刷题笔记——1.两数之和题目描述分析收获的全部内容，希望文章能够帮你解决leetcode刷题笔记——1.两数之和题目描述分析收获所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。