嗨客网搜索
两数之和

描述

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 是数组里面的数据索引。即使有两个相同的值,后面的数据位置会覆盖前面的数据,不会影响。

原先的数组结构如下:

01 数组原来结构.png

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

02 数组转map.png

我们可以遍历两次数组,第一次遍历的时可以组装 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 }

赞助商链接:


嗨客网顶部