- 描述
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, whereindex1 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
- 分析
用雙循環(huán)求解嗜逻，時(shí)間復(fù)雜度為O(n^2)
利用HashMap按key讀取value復(fù)雜度為O(1)這個(gè)特性则北，將數(shù)組元素的值作為key瞬女，下標(biāo)作為value，這樣可以很快獲得相應(yīng)元素的下標(biāo)，這樣時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)
package leet.TwoSum;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public static int[] getTwoSum(int[] arr, int target) {
int[] result = new int[2];
// 利用HashMap按key讀取復(fù)雜度為O(1)這個(gè)特性，
// 將數(shù)組的元素值作為key蚓再，下標(biāo)作為value，這樣可以很快獲得相應(yīng)元素的下標(biāo)
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < arr.length; ++i) {
if(!map.containsKey(arr[i]))
map.put(arr[i], i);
int n = target - arr[i];
if(map.containsKey(n) && map.get(n) != null && map.get(n)<i) {
result[1] = i + 1;
result[0] = map.get(n) + 1;
return result;
}
}
return result;
}
}
