leetcode算法题—golang—两数之和（题1）

题目：两书之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

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

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

方法一，时间复杂度 n*n

 //方法一 时间复杂度： n*n
func twoSum(nums []int, target int) []int {
	for i,v := range nums{
		if i == len(nums)-1{
			return []int{-1,-1}
		}
		for j :=i+1;j<len(nums);j++{
			if res := v+nums[j];res==target{
				return []int{i,j}
			}
		}
	}

	return []int{-1,-1}
}

方法二：两遍哈希表，时间复杂 O(n)

func twoSum(nums []int, target int) []int {
	maps := make(map[int]int)

	for i,v := range nums{
		maps[v] = i
	}

	//然后在map中寻找符合target的要求的值
	for i,v := range nums{
		temp := target - v
		//找出的这个数不要是本身
		if _,isok := maps[temp];isok && maps[temp] !=i{
			return []int{i,maps[temp]}
		}
	}
	return []int{-1,-1}
}

方法三：一遍哈希表 时间复杂度O(n)

func twoSum(nums []int, target int) []int {
	maps := make(map[int]int)
	for i,v := range nums{
		temp := target - v
		if i2,isok := maps[temp];isok{
			//如果有的
			return []int{i2,i}
		}
		//添加
		maps[v] = i
	}
	return []int{-1,-1}
}

推荐：方法三