20
golang刷LeetCode[0001] 两数之和
source link: https://studygolang.com/articles/25678
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目描述
给定一个整数数组 nums 和一个目标值 target ，请你在该数组中找出和未目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一种答案。但是，你不能重复利用这个数组中同样的元素。
示例：
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0，1]
题解
- 第一种方法
func twoSum(nums []int, target int) []int {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i] + nums[j] == target {
return []int{i,j}
}
}
}
return nil
}
两重循环遍历元素，比较获取 target ，这就是俗称的暴力法
暴力破解法
那么有没有什么方法简化呢？
- 第二种方法
func twoSum(nums []int, target int) []int {
var m = make(map[int]int)
for i:=0; i<len(nums);i++ {
res := target - nums[i]
if _,ok:=m[res];ok{
return []int{m[res],i}
}
m[nums[i]] = i
}
return nil
}
遍历列表，将元素放入map中，根据 target 与当前数的相减可以在map中找出另一个数。
hash算法
答：题目中已经声明不能使用重复元素。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK