文档章节

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
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
划分数组为两个和相等的子集 Partition Equal Subset Sum

问题: Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. N......

叶枫啦啦
01/04
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

没有更多内容

加载失败,请刷新页面

加载更多

GO冒泡,二分查找

package mainimport("fmt")func main() {var arr [5]int = [5]int{11,13,9,2,25}maopao(&arr)fmt.Println("arr = ", arr) //[2 9 11 13 25]findIndex := binaryFind(&arr, 0......

汤汤圆圆
10分钟前
1
0
工作2年半跳槽面试阿里,成功拿到offer,凭什么?

2015年刚毕业的我,进入了一家小小的公司实习工作,在学校学了三年软件开发的我,还是想去寻找一份互联网行业的工作,这样更能学以致用发挥自己的特长。一直到18年三月份,我辞掉已有的工作,...

java知识分子
14分钟前
1
0
讲述下:Linux的10个最危险的命令

导读 Linux命令行佷有用、很高效,也很有趣,但有时候也很危险,尤其是在你不确定你自己在正在做什么时候。这篇文章将会向你介绍十条命令,但你最好不要尝试着去使用。 当然,以下命令通常都...

问题终结者
18分钟前
1
0
分库分表后如何部署上线?

引言 我们先来讲一个段子 面试官:“有并发的经验没?” 应聘者:“有一点。” 面试官:“那你们为了处理并发,做了哪些优化?” 应聘者:“前后端分离啊,限流啊,分库分表啊。。” 面试官:...

Java烂猪皮
23分钟前
1
0
Redis源码阅读笔记-快速列表

快速列表 快速列表(quicklist)是由压缩列表(ziplist)组成的一个双向链表,链表中,每一个节点都是以压缩列表(ziplist)的结构保存。 在 Redis3.2 后加入的新数据结构,在列表键中取代了双向链...

Jian_Ming
41分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部