Leetcode题1

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

import java.util.HashMap;
import java.util.Vector;

public class Solution {
    public  int[] twoSum(int[] numbers, int target)
    {
        int result[]= new int[2];
        HashMap<Integer,Vector<Integer>> aaa = new HashMap<Integer,Vector<Integer>>();
        for(int i=0;i<numbers.length;i++)
        {
            if( aaa.containsKey(numbers[i]) )
            {
                Vector<Integer> index = aaa.get(numbers[i]);
                index.add(i+1);
            }
            else
            {
                Vector<Integer> index = new Vector<Integer>();
                index.add(i+1);
                aaa.put(numbers[i], index);
            }
        }
        for(int i=0;i<numbers.length;i++)
        {
            int subTarget = target - numbers[i];
            if(aaa.containsKey(subTarget))
            {
                Vector<Integer> index = aaa.get(subTarget);
                for(int j = 0;j<index.size();j++)
                {
                    if(index.get(j)!=i+1)
                    {
                        result[0] = i+1;
                        result[1] = index.get(j);
                        return result;
                    }
                }
            }
        }
        return result;
    }
}

上面是个很笨的解法，下面是Discuss里面一个很酷的解法：

import java.util.HashMap;

public class Solution {

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

int[] result = new int[2];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

for(int i = 0; i < numbers.length; i++){
if(map.containsKey(numbers[i])){
result[0] = map.get(numbers[i]) + 1;
result[1] = i + 1;
}
map.put(target - numbers[i], i);
}
return result;
}
}

但是这个解法我有一点疑虑：

对于输入：1 4 2 2 6 5 8。 target：8

该程序会输出 4 5

但是实际上应该输出 3 5

但是上述代码在leetcode中是通过的，不知道是不是因为leetcode上的测试用例没有检测这种情况。