文档章节

1. Two Sum

Do0M
 Do0M
发布于 2017/08/26 21:35
字数 492
阅读 0
收藏 0
点赞 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
118
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
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
隐马尔科夫模型HMM(三)鲍姆-韦尔奇算法求解HMM参数

在本篇我们会讨论HMM模型参数求解的问题,这个问题在HMM三个问题里算是最复杂的。在研究这个问题之前,建议先阅读这个系列的前两篇以熟悉HMM模型和HMM的前向后向算法,以及EM算法原理总结,这...

citibank
06/15
0
0
递归

能实现下面的递归方法 for (int i = 1; i <= 10; i++) { int sum1 = 0; sum1 += Math.pow(i, 2); if (sum1 == 100) { System.out.println(i); } for (int j = 1; j <= i; j++) { int sum2 = ......

lzhphantom
2017/09/06
215
7
完美数 Perfect Number

问题: We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself. Now, given an integer n, write a function that ret......

叶枫啦啦
2017/06/27
0
0
mongdb 与 sql 数据库对照关系图

SQL Terms, Functions, and Concepts MongoDB Aggregation Operators WHERE $match GROUP BY $group HAVING $match SELECT $project ORDER BY $sort LIMIT $limit SUM() $sum COUNT() $sum j......

今天来找bug
2016/02/29
26
0
几个算法题

1 在一个字符串中找到第一个只出现一次的字符,如输入abac,则输出b 本题看似很简单,开个长度为256的表,对每个字符hash计数就可以了,但很多人写的代码都存在bug,可能会发生越界访问。这是...

泳泳啊泳泳
2017/12/25
0
0
包含k个数的最大子数组的平均值 Maximum Average Subarray I

问题: Given an array consisting of integers, find the contiguous subarray of given length that has the maximum average value. And you need to output the maximum average value. ......

叶枫啦啦
2017/08/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

什么是Base64

一、什么是Base64? 百度百科中对Base64有一个很好的解释:“Base64是网络上最常见的用于传输8Bit字节码的编码方式之一,Base64就是一种基于64个可打印字符来表示二进制数据的方法”。 什么是...

Jack088
3分钟前
0
0
SQL多表联查leftjoin左边加表单

SELECT IFNULL(u.USER_ACCOUNT, o.USER_ACCOUNT) u.USER_ACCOUNT, o.* FROM gh_orders o LEFT JOIN gh_user u ON o.PARENT_ID = u.ROW_ID 1.假如u.USER_ACCOUNT不空返回u.USER_ACCOUNT,否则返......

森火
7分钟前
0
0
expect脚本同步文件、expect脚本指定host和要同步的文件、构建文件分发系统

expect脚本同步文件 更改权限 执行脚本 查看执行结果 expect eof需要加上,作用是等脚本命令执行完再进行退出 expect脚本指定host和要同步的文件 更改权限,执行脚本 构建文件分发系统 需求背...

Zhouliang6
45分钟前
1
0
Hive应用:外部分区表

Hive应用:外部分区表 介绍 Hive可以创建外部分区表。创建表的时候,分区要在建表语句中体现。建完之后,你不会在表中看到数据,需要进行分区添加,使用alter语句进行添加。然后数据才会显示...

星汉
55分钟前
3
0
点击Enter登录

1. 效果 2. 实现过程(记得引入jq文件) //6.回车事件 登录 $(function() { document.onkeydown = function(event) { var e = event || window.event || arguments.callee.caller.arguments......

Lucky_Me
今天
1
0
点击菜单内容切换

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <style> .menu{ height: 38px; background-color: #eeeeee; line-height: 38px; } .mao{ ......

南桥北木
今天
1
0
OSChina 周六乱弹 —— 妹子和游戏哪个更好玩

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @andonny :分享唐朝乐队的单曲《国际歌》 《国际歌》- 唐朝乐队 手机党少年们想听歌,请使劲儿戳(这里) @举个栗子- :日常祈雨 邪恶的大祭...

小小编辑
今天
591
8
流利阅读笔记32-20180721待学习

“人工智能”造假:只有人工,没有智能 Lala 2018-07-21 1.今日导读 当今社会,擅长单个方面的人工智能已经盛行,手机借助 AI 智慧防抖技术帮助大家拍出清晰照片,谷歌研发的 AI 助手将可以帮...

aibinxiao
今天
10
0
我的成长记录(一)

今天突然精神抖擞,在我的博客下新开一项分类>成长记录,专门记录每隔一段时间我的一点感悟吧。因为今天才专门花时间新开这样一个分类,所以以前有过的一些感悟没有记录下来,现在已经想不起...

dtqq
今天
1
0
机器学习管理平台 MLFlow

最近工作很忙,博客一直都没有更新。抽时间给大家介绍一下Databrick开源的机器学习管理平台-MLFlow。 谈起Databrick,相信即使是不熟悉机器学习和大数据的工程湿们也都有所了解,它由Spark的...

naughty
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部