描述
給一個整數(shù)數(shù)組，找到兩個數(shù)使得他們的和等于一個給定的數(shù)?target蔗候。
你需要實現(xiàn)的函數(shù)twoSum需要返回這兩個數(shù)的下標, 并且第一個下標小于第二個下標市埋。注意這里下標的范圍是 0 到?n-1谋旦。
你可以假設(shè)只有一組答案。
樣例
給出 numbers =?[2, 7, 11, 15], target =?9, 返回?[0, 1].
挑戰(zhàn)
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值（即之前減法中減數(shù)的索引值）和此時的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快以政，但是提交測評好像時間都差不多霸褒，這個還不太清楚為什么。
