文档章节

1. Two Sum

Do0M
 Do0M
发布于 2017/08/26 21:35
字数 492
阅读 0
收藏 0

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的朋友,不知道怎么弄出来的。





本文转载自:http://blog.csdn.net/limk96/article/details/72805683

共有 人打赏支持
Do0M
粉丝 0
博文 8
码字总数 24
作品 0
私信 提问
UNIX环境下批量生产用户(原创:北京)

UNIX环境下批量生产用户 作者:viking_lee freenews88@yahoo.com.cn 原创作品 本例可用于Linux8.0/7.0 Solaris8 Linux 环境: 1.编写一个文件:passwd.list。目的是让计算机可识别出用户名。...

JavaGG
2009/05/06
249
0
二叉树的路径和(不必以根节点为起始)Path Sum III

问题: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at th......

叶枫啦啦
2017/08/07
0
0
关于 计算1/1-1/2+1/3-1/4+1/5 …… + 1/99 - 1/100 的值的体会

按照我最开始的思路就是执行下面的代码 #include #include int main() { int i=0; double sum1=0; double sum2=0; double sum=0; for(i=1;i<101;i++) { if(i%2==0) { sum1=sum1+1/i; } else ......

triorwy
2017/11/03
0
0
给大神们看条sql。看看如何优化,在不改变表结构得情况。

SELECT c.unit, sum(case when (i.deep=1 OR i.deep>1) and i.type=0 then s.deep1 else 0 end) AS deep1, sum(case when (i.deep=1 OR i.deep>1) and i.type=1 then s.deep1 else 0 end) AS......

kstsca
2013/03/13
202
3
shell脚本练习(12.11)

求100以内偶数的和 思路:1.先定义一个变量x 2.x的范围是0-50,x的初始值为1 3.和值初始值为0,每做一次循环 和值就等于本身+2*i 方法一: vim sum1.sh #!/bin/bash #written by lizheng #ab...

lizheng103
2016/12/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

开源软件会被云杀死吗 ?

本文转载云头条,原作者:Michael Stiefel是Reliable Software公司的负责人,是一名软件架构和开发顾问。 文章要点 虽然开源开发不会消失,但商业开源厂商的未来不是很有希望。随着全面管理的...

linuxCool
23分钟前
0
0
OSChina 周三乱弹 —— 谈什么对象?睡什么觉?

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @胖达panda :最肯忘却古人诗,最不屑一顾是相思。分享童丽的单曲《红豆生南国》: 《红豆生南国》- 童丽 手机党少年们想听歌,请使劲儿戳(这...

小小编辑
28分钟前
43
3
stylus

stylus基础教程,stylus实例教程,stylus语法总结

miaojiangmin
今天
3
0
PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
今天
2
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部