[LeetCode] Two Sum

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 

解题思路：
最直接的思路，就是遍历整个数组，对每个元素，从在它以后的数组中寻找是否存在一个元素，它们之和等于target。这种思路的时间复杂度为N*N。

我们要从数组中寻找一组数据，那至少会扫描一遍数组，也就是时间复杂度至少为N。那我们就想到可用HashMap来将搜素元素的时间复杂度降低为O(1)。当遍历数组时，对每个元素，我们用时间复杂度为O(N)来确认是否存在一个元素，它们的和为target. 但只需要O(1)用HashMap搜索target - num[i]是否存在。如果存在，则返回Index。这样我们就可以想到当遍历数组的时候，同时也建立HashMap, target-num[i]为Key, Index为value。

JavaCode:

public int[] twoSum(int[] numbers, int target) {
         HashMap index = new HashMap ();
           int[] result = new int[2];
           
           for(int i = 0; i < numbers.length; i ++){
               if(index.containsKey(numbers[i])){
                   result[0] = index.get(numbers[i]);
                   result[1] = i + 1;
                   
                   break;
               }
               
               index.put(target - numbers[i], i+1);
           }
           
           return result;
    }

Python:

class Solution:
 # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
     dict = {}
     for i in xrange(len(num)):
      newNum = target - num[i]
      if newNum in dict:
       return (dict[newNum] + 1, i + 1)
      dict.update({num[i]: i})