1.原题

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 same element twice.

Example:

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

2.题意

给定一个整形数组，一个整形目标值，找出这个数组中两个元素的下标，这两个元素之和等于目标值。比如数组nums是[2, 7, 11, 15]，目标值是9的话，那么nums[0] + nums[1]就等于9，所以返回[0, 1]

3.思路

• 首先需要明确数组是无序的。

• 其次需要知道，返回的是数组的下标不是这两个元素的值。所以不能使用排序后，两头往中间找的方式。

具体做法就是：

• 使用一个map保存元素数字与下标之间的映射关系。我们从前往后扫描数组，这个map只保存了从第一个元素，到当前待扫描元素的前一个元素。也就是说，待扫描元素之前的元素我们已经都保存了每个数值以及它对应的下标。

• 扫描当前元素时，我们用目标值target - nums[current]得到一个差值，这个差值可以理解为需要与当前元素nums[current]搭配形成target的“配偶”。我们在map中查找是够存在这个“配偶”，也就是说看看前面扫描的那堆元素里面是不是存在该元素的“配偶”。

• 如果找到“配偶”，返回【配偶的下标，当前元素的下标current】，如果没有找到，那就将当前元素以及对应的下标存入到map中。

4.代码实现

本系列的文章都会使用两种语言实现：java和python，也是笔者最近用的较多的，不排除后面会继续加入其它的语言。

java代码参见如下：

class Solution { public int[] twoSum(int[] nums, int target) { HashMap num_index = new HashMap();

        for(int i = 0; i < nums.length; i++) {

            if(num_index.containsKey(target - nums[i])) {

                return new int[] {num_index.get(target - nums[i]), i};

            }

            num_index.put(nums[i], i);

        }

        throw new IllegalArgumentException("No solution for two sum");

  }

}

python代码参见如下：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        num_index = {}
        for i in range(len(nums)):
            if target - nums[i] in num_index.keys():
                return [num_index.get(target - nums[i]), i]
            num_index[nums[i]] = i
        return []