两数之和

2020-03-03 18:07:51 134 0 leetcode

题目描述

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

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

示例:

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum

我的解答方式

func twoSum(nums []int, target int) []int { indexMap := make(map[int]int) for i, v := range nums { tmp := target - v if j,ok := indexMap[tmp];ok && i != j { if i > j { i, j = j, i } return []int{i,j} } indexMap[v] = i } return []int{} }

总结

题目其实很简单,通过暴力法也可以解答,只需要遍历 i 后再次根据遍历找出 j 即可,然而这个方法在时间上有很大牺牲,因为需要进行双重的遍历,时间复杂度为 O(n²)

所以选择以空间换时间,使用哈希表来记录已出现的元素以及其下标,这样就不需要每次都根据 i 来再次遍历出 j 了,只需在 map 中查找是否有 j 所对对应的值即可。如此一来,时间复杂度为 O(n)

提交结果

评论

:doodle { @grid: 32 / 100vmax; } @random { border-top: 1px solid #60569e; } @random { border-left: 1px solid #60569e; } @random(.2) { :after { content: ''; background: hsl(@rand(360), 60%, 70%); @size: @rand(3px); } }