描述
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
你可以假设只有一组答案。
样例
给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].
挑战
Either of the following solutions are acceptable:
O(n) Space, O(nlogn) Time
O(n) Space, O(n) Time
V1:
暴力穷举法，此方法时间复杂度效率是O(n2)
class Solution:
"""
@param numbers: An array of Integer
@param target: target = numbers[index1] + numbers[index2]
@return: [index1, index2] (index1 < index2)
"""
def twoSum(self, numbers, target):
# write your code here
for i in range(len(numbers)):
for j in range(i+1,len(numbers)):
t = numbers[i] + numbers[j]
if t == target:
return i,j
V2:
令 t = target - numbers[i] ，将t作为key值，i作为value值存入字典p中，将第i+1个numbers依次与字典p里的键值比较，若有相同的则返回字典中的value值（即之前减法中减数的索引值）和此时的i值。
python版：
class Solution:
"""
@param numbers: An array of Integer
@param target: target = numbers[index1] + numbers[index2]
@return: [index1, index2] (index1 < index2)
"""
def twoSum(self, numbers, target):
# write your code here
p = {}
for i in range(len(numbers)):
t = target - numbers[i]
if numbers[i] in p:
return p[numbers[i]],i
else:
p[t] = i
Java版：
public class Solution {
/**
* @param numbers: An array of Integer
* @param target: target = numbers[index1] + numbers[index2]
* @return: [index1, index2] (index1 < index2)
*/
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
int[] res = new int[2];
for(int i=0;i<numbers.length;i++){
m.put(numbers[i],i);
}
for(int i=0;i<numbers.length;i++){
int t = target - numbers[i];
if(m.containsKey(t) && m.get(t) != i){
res[0] = i;
res[1] = m.get(t);
break;
}
}
return res;
}
}
按道理说V2会比V1快，但是提交测评好像时间都差不多，这个还不太清楚为什么。
