用java hashmap做two sum提交通不过

各位大神，能看看怎么回事吗，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;

        }
        
   
}

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. 
   
4.                          if (key == null) table.put(numbers [ i ], i);
   
5.                          else {
   
6.                             answer[1]=i+1;
   
7.                             answer[0]=key+1;
   
8.                             return answer;
   
9.                          }
   
10.                  }

复制代码

没细看你的代码，因为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-19 10:46
我试了，还是超时

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

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

请你考虑Input: numbers={1，1}, target=2

weihu816 发表于 2015-4-18 20:28
请你考虑Input: numbers={1，1}, target=2

可以通过啊，leetcode上显示是time limitation，不知道咋回事

weihu816 发表于 2015-4-18 20:28
请你考虑Input: numbers={1，1}, target=2

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

warriorbrant 发表于 2015-4-18 21:28
额，其实是误打误撞把重复情况考虑进去了，你提醒，我也以为有错，后来没想到歪打正着了

额 扫了一眼没仔细看。。按判断条件是考虑了。。楼上正解

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

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

stellari 发表于 2015-4-18 22:50
确实是O(n)的算法没错，但是，你的每次循环中，在最坏情况下，有3次table查询。如果table查询是这个程 ...

我试了，还是超时

stellari 发表于 2015-4-19 11:02
如果是严格用5楼中的循环替换掉原来的循环（而没有做任何其他的事），超时的概率是非常非常之低的，除非 ...

现在又通过了，刚才可能是后台有问题，thx！