赞
赏
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 集合中。如果在并且和当前的数据的位置不是同一个位置,那么就得到了数据位置,如果不在,那么就判断接下来的数据。
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;
}
}
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
}