两数之和

描述

leetcode 官方第 1 题，给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例3:

输入：nums = [3,3], target = 6
输出：[0,1]

思路

求两个数之和，我们可以换一个思路，就是已经知道了一个数值和两个数值之和，那么我们就可以得到另外一个数值，再判断另外一个数值是否在剩下的数组里面即可。

题目的前提假设条件是每个组合就只能够有一组答案，并且一个数值被计算后不能再次计算，所以我们可以使用 Map 来组装数据。因为该函数的最终结果是要返回对应数值的索引信息，所以我们可以定义一个 map 结构的数据。它的 key 是数组里面的值， value 是数组里面的数据索引。即使有两个相同的值，后面的数据位置会覆盖前面的数据，不会影响。

原先的数组结构如下：

我们遍历一次数组，将数据维护到 Map 集合中去，我们以数组中的值为 key，值的索引位置为 value。结果如下：

我们可以遍历两次数组，第一次遍历的时可以组装 map 数据结构的数据。

第二次遍历的时候用传递的数据之和减去当前被遍历到的数值。然后判断剩下的一个值是否在 map 的 key 集合中。如果在并且和当前的数据的位置不是同一个位置，那么就得到了数据位置，如果不在，那么就判断接下来的数据。

代码具体实现

Java语言版本

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //定义返回值
        int[] retValue = new int[2];
        Map<Integer,Integer> numMap = new HashMap();
        //遍历数据一次，将值为key，对应的值索引位置为值存放在 map 中
        for(int i=0;i<nums.length;i++){
            numMap.put(nums[i],i);
        }
        //遍历具体数组
        for(int i=0;i<nums.length;i++){
            //求出另外一个需要被相加的值
            int otherValue = target - nums[i];
            //判断另外一个需要被相加的值是否在 map 集合中，并且不是同一个位置的元素
            if(numMap.get(otherValue) != null && numMap.get(otherValue) != i ){
                retValue[0] = i;
                retValue[1] = numMap.get(otherValue);
                return retValue;
            }
        }
        return retValue;
    }
}

Go语言版本

func twoSum(nums []int, target int) []int {
    //定义返回值
   retValue := make([]int, 0, 2)
   numMap :=  make(map[int]int, len(nums))
   //遍历数据一次，将值为key，对应的值索引位置为值存放在 map 中
   for i := 0; i < len(nums); i++ {
      numMap[nums[i]] = i
   }
   for i := 0; i < len(nums); i++ {
      //求出另外一个需要被相加的值
       otherValue := target - nums[i]
      //判断另外一个需要被相加的值是否在 map 集合中，并且不是同一个位置的元素
      if numMap[otherValue] != 0 && numMap[otherValue] != i {
          retValue = append(retValue,i)
          retValue = append(retValue,numMap[otherValue])
         return  retValue
      }
   }
   return retValue
}