Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the sameelement twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

Related Topic: Array, Hash Table

解题思路：这是LC一道经典题，考虑使用HashMap来保存input中值与其数组index的对应关系。在遍历数组的过程中，若target减去当前遍历值在HashMap中存在，则证明已找到对应的两个值，找到其index返回结果即可，反之则将当前遍历点写入HashMap。

Time Complexity: O(n), Space Complexity: O(n)

Java版本：

1 class Solution { 2     public int[] twoSum(int[] nums, int target) { 3         int[] result = new int[2]; 4         if (nums == null || nums.length < 2) { 5             return result; 6         } 7          8         Map
     
       map = new HashMap
      
       (); 9         10         for (int i = 0; i < nums.length; i++) {11             if (map.containsKey(target - nums[i])) {12                 result[0] = map.get(target - nums[i]);13                 result[1] = i;14             }15             map.put(nums[i], i);16         }17         18         return result;19     }20 }
      
     

 

JavaScript版本：

1 /** 2  * @param {number[]} nums 3  * @param {number} target 4  * @return {number[]} 5  */ 6 var twoSum = function(nums, target) { 7     var result = new Array(2); 8     if (nums == null || nums.length < 2) { 9         return result;10     }11     12     var map = new Map();13     14     for (var i = 0; i < nums.length; i++) {15         if (map.has(target - nums[i])) {16             result[0] = map.get(target - nums[i]);17             result[1] = i;18         }19         map.set(nums[i], i);20     }21     22     return result;23 };

 

Python版本：

1 class Solution: 2     def twoSum(self, nums: List[int], target: int) -> List[int]: 3         result = [None] * 2 4         if len(nums) < 2: 5             return result 6          7         dict = {} 8          9         for i in range(len(nums)):10             if (target - nums[i]) in dict:11                 result[0] = dict.get(target - nums[i])12                 result[1] = i13             14             dict[nums[i]] = i15         16         return result