一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 815|回复: 11
收起左侧

[Leetcode] 用java hashmap做two sum提交通不过

[复制链接] |试试Instant~ |关注本帖
warriorbrant 发表于 2015-4-18 19:22:12 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
各位大神,能看看怎么回事吗,hashmap做的话不是O(n)吗,怎么还通不过呢

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

public class Solution {
   public int[] twoSum(int[] numbers, int target) {

                HashMap<Integer, Integer> table = new HashMap<Integer, Integer>();

                Integer key;
               
                int[] answer = new int[2];
               
                for (int i = 0; i < numbers.length; i++) {

                        key = table.get(numbers[i]);

                        if (key == null)
                                table.put(numbers[i], i);

                        key = table.get(target - numbers[i]);

                        if (key != null) {
                               
                                if(i<key){
                                        answer[0]=i+1;
                                        answer[1]=key+1;
                                        return answer;
                                }
                               
                                if(i>key){
                                        answer[1]=i+1;
                                        answer[0]=key+1;
                                        return answer;
                                }
                               
                        }

                }
                return null;

        }
        
   
}
weihu816 发表于 2015-4-18 20:28:43 | 显示全部楼层
请你考虑Input: numbers={1,1}, target=2
回复 支持 反对

使用道具 举报

 楼主| warriorbrant 发表于 2015-4-18 21:25:23 | 显示全部楼层
weihu816 发表于 2015-4-18 20:28
请你考虑Input: numbers={1,1}, target=2

可以通过啊,leetcode上显示是time limitation,不知道咋回事
回复 支持 反对

使用道具 举报

 楼主| warriorbrant 发表于 2015-4-18 21:28:12 | 显示全部楼层
weihu816 发表于 2015-4-18 20:28
请你考虑Input: numbers={1,1}, target=2

额,其实是误打误撞把重复情况考虑进去了,你提醒,我也以为有错,后来没想到歪打正着了
回复 支持 反对

使用道具 举报

stellari 发表于 2015-4-18 22:50:32 | 显示全部楼层
warriorbrant 发表于 2015-4-18 21:28
额,其实是误打误撞把重复情况考虑进去了,你提醒,我也以为有错,后来没想到歪打正着了


确实是O(n)的算法没错,但是,你的每次循环中,在最坏情况下,有3次table查询。如果table查询是这个程序中最耗时的地方,那么整个程序就会比较慢,也就无法通过OJ上预设的时间阈值。

你不如用下面的方法:即每遇到一个numbers中的数,就在map中找其补数。若找到则立即返回,若未找到则将此数加入map:
  1.                  for (int i = 0; i < numbers.length; i++) {
  2.                          key = table.get(target - numbers [ i ]);

  3.                          if (key == null) table.put(numbers [ i ], i);
  4.                          else {
  5.                             answer[1]=i+1;
  6.                             answer[0]=key+1;
  7.                             return answer;
  8.                          }
  9.                  }
复制代码
回复 支持 反对

使用道具 举报

weihu816 发表于 2015-4-18 23:17:09 | 显示全部楼层
warriorbrant 发表于 2015-4-18 21:28
额,其实是误打误撞把重复情况考虑进去了,你提醒,我也以为有错,后来没想到歪打正着了

额 扫了一眼没仔细看。。按判断条件是考虑了。。楼上正解
回复 支持 反对

使用道具 举报

weihu816 发表于 2015-4-18 23:17:46 | 显示全部楼层
weihu816 发表于 2015-4-18 23:17
额 扫了一眼没仔细看。。按判断条件是考虑了。。楼上正解

因为Hashmap只有在内存足够大的情况下我们才能看作O(1)的get
回复 支持 反对

使用道具 举报

 楼主| warriorbrant 发表于 2015-4-19 10:46:58 | 显示全部楼层
stellari 发表于 2015-4-18 22:50
确实是O(n)的算法没错,但是,你的每次循环中,在最坏情况下,有3次table查询。如果table查询是这个程 ...

我试了,还是超时
回复 支持 反对

使用道具 举报

stellari 发表于 2015-4-19 11:02:33 | 显示全部楼层

如果是严格用5楼中的循环替换掉原来的循环(而没有做任何其他的事),超时的概率是非常非常之低的,除非你测试时OJ的后台服务器出现了问题。如果是这种情况,你可稍后再进行测试(比如说现在)。

如果你自己对这段循环做了其他改动,那么更可能是这段改动引起的问题。如果是这样,请把你改动后的完整代码贴出来。
回复 支持 反对

使用道具 举报

 楼主| warriorbrant 发表于 2015-4-19 11:35:42 | 显示全部楼层
stellari 发表于 2015-4-19 11:02
如果是严格用5楼中的循环替换掉原来的循环(而没有做任何其他的事),超时的概率是非常非常之低的,除非 ...

现在又通过了,刚才可能是后台有问题,thx!
回复 支持 反对

使用道具 举报

Kimurate 发表于 2015-4-19 11:42:08 | 显示全部楼层
没细看你的代码,因为hashmap解法不可能超时……
我贴一下我的吧,应该比较简洁
  1.     public int[] twoSum(int[] numbers, int target) {
  2.         Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  3.         for (int i=0; i<numbers.length; i++) {
  4.             if (!map.containsKey(numbers[i])) {
  5.                 map.put(target - numbers[i], i);
  6.             } else {
  7.                 int[] rt = {map.get(numbers[i])+1, i+1};
  8.                 return rt;
  9.             }
  10.         }
  11.         int[] rt = {};
  12.         return rt;
  13.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| warriorbrant 发表于 2015-4-20 15:23:05 | 显示全部楼层
Kimurate 发表于 2015-4-19 11:42
没细看你的代码,因为hashmap解法不可能超时……
我贴一下我的吧,应该比较简洁

已经通过了,thx!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 20:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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