两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

使用hash表存储目标值与数组元素之差(key)和该数组元素的索引(value),当剩余的素组中有元素是hash表中的,则找到了一组符合题目要求的解。

具体思路

  1. 开始循环给定数组nums,获得其中元素的索引index、值num;
  2. 在Hash表中查找是否有值为num的key,若有则找到题解,若没有执行下一步
  3. 将key=target-num,value=index存入Hash表
  4. 进入下一次循环

注意:将第2步放在第三步前是为了满足“你不能重复利用这个数组中同样的元素”这个条件

步骤实现

package main

import "fmt"

func main() {
	nums := []int{2, 7, 11, 15}
	target := 9
	fmt.Println(sum(nums, target))
}

func sum(nums []int, target int) []int {
	hM := make(map[int]int, len(nums))

	for index, num := range nums {
		if value, ok := hM[num]; ok {
			nums = nums[:2]
			nums[0] = value
			nums[1] = index
			return nums
		}

		hM[target-num] = index
	}
	return nil
}