Problem###
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
Analysis###
關(guān)鍵是尋找兩個合適的數(shù)
最先以為序列式有序的，結(jié)果不是引镊；
然后直接窮舉所用組合，結(jié)果會超時吩抓；
最后使用HashMap來實(shí)現(xiàn)亮瓷，key = 數(shù)的值，value = 數(shù)的位置：首先將所有的數(shù)與其位置存儲于Map中嘱支，然后對于每個數(shù)去檢測能和它組合成target的數(shù)的位置蚓胸，如果沒有除师，就下一個。
Tips###
1：numbers 是無序的汛聚！
2：窮舉會超時！:
3：如果Hash搜索的時候是按numbers的順序從前往后找的話倚舀，其本身就是index1小，index2大痕貌。
Implementation###
package twosum; import java.util.HashMap; public class Solution { public int[] twoSum(int[] numbers, int target) { HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i = 0 ; i < numbers.length ; i++){ map.put(numbers[i], i); } for(int i = 0 ; i < numbers.length ; i++){ int left = target - numbers[i]; if(map.get(left) != null && map.get(left) != i){ int[] indexs = {(i+1),(map.get(left)+1)}; return indexs; } } return null; } }
