1. Two Sum
博客专区 > Do0M 的博客 > 博客详情
1. Two Sum
Do0M 发表于8个月前
1. Two Sum
  • 发表于 8个月前
  • 阅读 0
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

此题有两解,普通的搜索和哈希表。

普通的搜索(100ms):

int* twoSum(int* nums, int numsSize, int target) {
    int i=0,j=0;
    int*res = NULL;
    res = malloc(2*sizeof(int));
    res[0]= res[1]= 0;
    for(i=0;i<numsSize;i++){
        for(j=i+1;j<numsSize;j++){
            if(nums[i]+nums[j]==target){
                res[0]=i;
                res[1]=j;
                return res;
            }
        }
    }
    return res;
}

哈希表(3ms):

int* twoSum(int* nums, int numsSize, int target) {//待测数组  数组里的数据个数 要求的和
    int i=0,min=nums[0];;
    int*indices=malloc(2*sizeof(int));//indices二元组用来保存,输出结果
    for(i=1;i<numsSize;i++){
        min=nums[i]<min?nums[i]:min;
    }//求出数组最小值
    int hash[target-2*min+1];//建立哈希表,数值为min~target-min,因为测试数据中有负值元素,所以哈希查找时都减去min归零。
    for(i=0;i<target-2*min+1;i++){
        hash[i]=INT_MIN;
    }//初始化哈希表,因为测试数据的target有0,所以只能设成INT_MIN
    for(i=0;i<numsSize;i++){
        if(nums[i]>target-min){
            continue;
        }//哈希表越界了,也就是说,这个数组元素值所需要的另一个值小于min
        if(hash[nums[i]-min]==INT_MIN){
            hash[target-nums[i]-min]=i;
        }//把一个数组元素对应的另一个元素号当作key,把该数组元素设成key对应的value
        else{//发现value不再是初始值INT_MIN,已经被更改过,即,有对应的另一个元素了
            indices[0]=hash[nums[i]-min];
            indices[1]=i;//一对元素小值出现时大值未出现,小值把自己的元素号赋给大值的value,大值查看value时就能找到小值的元素号。
            return indices;
        }
    }
    return NULL;
}


LeetCode上哈希表大概是5%的水平,搜索大概是50%的水平,还有结果0ms的朋友,不知道怎么弄出来的。





  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 8
码字总数 24
×
Do0M
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: