找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2300|回复: 16
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Two sum】-【刷题第一弹】

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 10-23-2014 06:20 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:46 AM 编辑

快速通道:
https://oj.leetcode.com/problems/two-sum/


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================


思路:暴利法,O(n^2),如果可以用hashmap的话,先把元素存map,再遍历一次,判断target-a是否在map中

java代码:
  1. public int[] twoSum(int[] numbers, int target) {
  2.         if(numbers==null||numbers.length==0)    return new int[]{-1,-1};;
  3.         int i=0,j=0,n=numbers.length;
  4.         HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
  5.         for(i=0;i<n;++i){
  6.             map.put(numbers【i】,i+1);
  7.         }
  8.                 for(i=0;i<n;++i){
  9.                         Integer index = map.get(target-numbers【i】);
  10.                         if(index!=null&&index!=i+1){
  11.                             return new int[]{i+1,index};
  12.                         }
  13.                 }
  14.                 return new int[]{-1,-1};
  15.     }
复制代码


复杂度:O(n)

本帖被以下淘专辑推荐:

发表于 11-8-2014 09:42 AM | 显示全部楼层
有一点比较好奇,
hashmap的话,如果有两个重复的数字,应该会把后面那个的index给覆盖掉。
比如3,2,2,4. target是4
在put map的时候你put了<2, 2>,当put<2, 3>的时候,应该会只剩下<2, 3>没有了<2, 2>
这一点我试过,确实map会只剩下{2=3, 3=1, 4=4}
但是很神奇的是,用你的这个function确实可以找出来最后结果,index1=2,index2=3.
你知道为什么吗?
回复 支持 反对

使用道具 举报

0

主题

0

精华

108

积分

资深会员

Rank: 2

积分
108
发表于 11-8-2014 10:08 AM | 显示全部楼层
michael 发表于 11-8-2014 09:42 AM
有一点比较好奇,
hashmap的话,如果有两个重复的数字,应该会把后面那个的index给覆盖掉。
比如3,2,2 ...

应该每次先查找找不到再put
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表