2019年08月12日【LeekCode题库problem-1】
CoffeeRabbit · · 1739 次点击 · · 开始浏览GitHub 地址:coffeeTu-code
LeekCode 地址:题库
Language:Golang
/*
@题目(Two Sum)
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
@示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
@题目大意
在数组中找到 2 个数之和等于给定值的数字,结果返回 2 个数字在数组中的下标。
@解题思路
这道题最优的做法时间复杂度是 O(n)。
顺序扫描数组,对每一个元素,在 map 中找能组合给定值的另一半数字,如果找到了,直接返回 2 个数字的下标即可。如果找不到,就把这个数字存入 map 中,等待扫到"另一半"数字的时候,再取出来返回结果。
*/
func twoSum(nums []int, target int) []int {
var (
ok bool
index,
another int
)
numMap := make(map[int]int, len(nums))
for index, _ = range nums {
another = target - nums[index]
if _, ok = numMap[another]; ok {
return []int{numMap[another], index}
}
numMap[nums[index]] = index
}
return nil
}
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
GitHub 地址:coffeeTu-code
LeekCode 地址:题库
Language:Golang
/*
@题目(Two Sum)
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
@示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
@题目大意
在数组中找到 2 个数之和等于给定值的数字,结果返回 2 个数字在数组中的下标。
@解题思路
这道题最优的做法时间复杂度是 O(n)。
顺序扫描数组,对每一个元素,在 map 中找能组合给定值的另一半数字,如果找到了,直接返回 2 个数字的下标即可。如果找不到,就把这个数字存入 map 中,等待扫到"另一半"数字的时候,再取出来返回结果。
*/
func twoSum(nums []int, target int) []int {
var (
ok bool
index,
another int
)
numMap := make(map[int]int, len(nums))
for index, _ = range nums {
another = target - nums[index]
if _, ok = numMap[another]; ok {
return []int{numMap[another], index}
}
numMap[nums[index]] = index
}
return nil
}