1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 13, 2014
4+ Problem: Two Sum
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/two-sum/
7+ Notes:
8+ Given an array of integers, find two numbers such that they add up to a specific target number.
9+
10+ The function twoSum should return indices of the two numbers such that they add up to the target,
11+ where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
12+
13+ You may assume that each input would have exactly one solution.
14+
15+ Input: numbers={2, 7, 11, 15}, target=9
16+ Output: index1=1, index2=2
17+
18+ Solution: 1. Hash table. O(n)
19+
20+ Note: Hash Table solution has been updated. In case that the two elements are the same,
21+ all the indices should be stored in the map.
22+ */
23+
24+ public class Solution {
25+ public int []twoSum (int []numbers ,int target ) {
26+ HashMap <Integer ,Integer >map =new HashMap <Integer ,Integer >();
27+ for (int i =0 ;i <numbers .length ; ++i ) {
28+ int b =target -numbers [i ];
29+ if (map .get (b ) !=null ) {
30+ return new int []{map .get (b ),i +1 };
31+ }else map .put (numbers [i ],i +1 );
32+ }
33+ return null ;
34+ }
35+ }
